Graph property

From Wikipedia, the free encyclopedia
An example graph, with the properties of being planar and being connected, and with order 6, size 7, diameter 3, girth 3, vertex connectivity 1, and degree sequence <3, 3, 3, 2, 2, 1>

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.

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.

A graph property is sometimes called monotone increasing (or respectively monotone decreasing) if it is kept under the addition (respectively, the deletion) of edges. For example, the property of being connected is monotone increasing, whereas the property of being 3-colorable is monotone decreasing.[6]

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.

Some examples of graph properties

Some graph invariants

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
  • betweenness centrality
  • 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
  • isoperimetric number
  • arboricity
  • graph genus
  • pagenumber
  • Hosoya index
  • Wiener index
  • Estrada index
  • Colin de Verdière graph invariant
  • boxicity
  • strength

Sequences and polynomials

See also

References

  1. ↑ R. Diestel, Graph Theory, 3rd edition, Heidelberg:Springer-Verlag, 2005.
  2. ↑ S. Kreutzer, Algorithmic Meta-Theorems, 2008
  3. ↑ I. Averbouch, B. Godlin, and J.A. Makowsky, An extension of the bivariate chromatic polynomial, 2008.
  4. ↑ Alon, Noga; Shapira, Asaf (2008), "Every monotone graph property is testable", SIAM Journal on Computing 38 (2): 505–522, doi:10.1137/050633445 
  5. ↑ 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 0-8218-0963-6 p. 214
  6. ↑ Friedgut, Ehud (2005), "Hunting for sharp thresholds", Random Structures & Algorithms 26 (1-2): 37–51, doi:10.1002/rsa.20042, MR 2116574 .
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.