Graph property
From Wikipedia, the free encyclopedia
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.
Contents |
[edit] Definitions
While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph.
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".
More formally, a graph property is a class of graphs, i.e. a function from graphs to {T,F}, and a graph invariant is a function from graphs to some other set,[1] such as to the natural numbers (for scalar invariants),[2] or to (possibly ordered) sequences of natural numbers (for properties like the degree sequence), or to a polynomial ring,[3] such that isomorphic graphs have the same value.
A graph property is often called hereditary if it also holds for (is "inherited" by) its induced subgraphs.[4] A property is called additive if it is closed under disjoint union.[5] The property of being planar is both hereditary and additive, for example, since a subgraph of a planar graph must be planar, and a disjoint union of two planar graphs must also be planar. The property of being connected is neither, since a subgraph of a connected graph need not be connected, and a disjoint union of two connected graphs cannot be connected.
[edit] Graph invariants and graph isomorphism
Easily computable graph invariants are instrumental for fast recognition of graph isomorphism, or rather non-isomorphism, since for any invariant at all, two graphs with different values cannot (by definition) be isomorphic. Two graphs with the same invariants may or may not be isomorphic, however.
A graph invariant I(G) is called complete if the identity of the invariants I(G) and I(H) implies the isomorphism of the graphs G and H. Finding such an invariant would imply an easy solution to the challenging graph isomorphism problem. However, even polynomial-valued invariants such as the chromatic polynomial are not usually complete. The claw graph and the path graph on 4 vertices both have the same chromatic polynomial, for example.
[edit] Some graph invariants
[edit] Scalars
- order - the number of vertices
- size - the number of edges
- diameter - the longest of the shortest path lengths between pairs of vertices
- girth - the length of the shortest cycle contained in the graph
- clustering coefficient
- vertex connectivity - the smallest number of vertices whose removal disconnects the graph
- edge connectivity - the smallest number of edges whose removal disconnects the graph
- independence number - the largest size of an independent set of vertices
- clique number - the largest order of a complete subgraph
- algebraic connectivity
- vertex chromatic number - the minimum number of colors needed to color all vertices so that adjacent vertices have a different color
- edge chromatic number - the minimum number of colors needed to color all edges so that adjacent edges have a different color
- vertex covering number - the minimal number of vertices needed to cover all edges
- edge covering number - the minimal number of edges needed to cover all vertices
- arboricity
- graph genus
- pagenumber
- Hosoya index
- Wiener index
- Colin de Verdière graph invariant
- boxicity
- strength
[edit] Sequences and Polynomials
- degree sequence
- characteristic polynomial of the adjacency matrix
- chromatic polynomial – the number of k-colorings viewed as a function of k
- Tutte polynomial – a bivariate function that encodes much of the graph’s connectivity
[edit] See also
[edit] References
- ^ R. Diestel, Graph Theory, 3rd edition, Heidelberg:Springer-Verlag, 2005. [1]
- ^ S. Kreutzer, Algorithmic Meta-Theorems, 2008. [2]
- ^ I. Averbouch, B. Godlin, and J.A. Makowsky, An extension of the bivariate chromatic polynomial, 2008. [3]
- ^ Alon, Noga; Shapira, Asaf (2008), "Every monotone graph property is testable", SIAM Journal on Computing 38 (2): 505-522, doi:, http://www.math.tau.ac.il/~nogaa/PDFS/monotone1.pdf
- ^ 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 p. 214
