- Graph property
In

graph theory a**graph property**is any "inherently graph-theoretical" property of graphs (formal definitions follow), distinguished from properties of graphs described in terms of various graph representations:graph drawing s, data structures for graphs,graph labeling s, etc.**Definitions**While graph drawing and graph representation are valid topics in graph theory, in order to focus on "inherently graph-theoretical" properties of graphs, a

**graph property**is defined to be a property preserved under all possible isomorphisms of a graph.Graphs with the same graph property naturally define a certain family of graphs: the ones that have the specified property. Therefore, to avoid the ambiguity of the English word "property" and a feeling of

circular logic in the definition, a**graph property**is defined as a nonempty propersubset of the set of graphs closed under the graph isomorphism. [*Peter Mihok (1999) "Reducible properties and uniquely partitionable graphs" in: Ronald L. Graham, "Contemporary Trends in Discrete Mathematics", DIMASC Series in Discrete Mathematics and Computer Science, vol. 49, ISBN 0821809636 [*]*http://books.google.com/books?id=aE_-qdthsWcC&pg=PA217&lpg=PA217&dq=%22induced+hereditary+property%22&source=web&ots=Q_sGAk5c73&sig=7pQOu-zaI8tSABMncyewDU9RyJM#PPA213,M1 p. 213*]Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant".

Formally, a

**graph invariant**is anindexed family of graph properties.For example "the number of vertices" is an indexed family of graph properties "a graph has M edges, M = 0, 1, 2....". In this case the family of properties is indexed by the set of nonnegative integer numbers. A more complex example of graph invariant is the

degree sequence of a graph: the family of properties is indexed by the set of all ordered sequences of nonnegative integers.**Graph invariants*** number of vertices

* number of edges

*vertex chromatic number - minimum number of colors needed to color all vertices so thatadjacent vertices have a different color

*edge chromatic number - minimum number of colors needed to color all edges so thatadjacent edges have a different color

*edge covering number - minimal number of edges needed to cover all vertices

*vertex covering number - minimal number of vertices needed to cover all edges

*degree sequence

*graph genus **Types of graph properties***

Hereditary property (also calledmonotone property ): a property closed under the operation of taking subgraphs

*Additive graph property: a property closed under thegraph union [*Peter Mihok (1999) "Reducible properties and uniquely partitionable graphs" in: Ronald L. Graham, "Contemporary Trends in Discrete Mathematics", DIMASC Series in Discrete Mathematics and Computer Science, vol. 49, ISBN 0821809636 [*] For example, being an*http://books.google.com/books?id=aE_-qdthsWcC&pg=PA217&lpg=PA217&dq=%22induced+hereditary+property%22&source=web&ots=Q_sGAk5c73&sig=7pQOu-zaI8tSABMncyewDU9RyJM#PPA213,M1 p. 214*]acyclic graph is an additive property.**ee also***

Topological index **References**

*Wikimedia Foundation.
2010.*