Graph property

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.[1]

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 with the property that any two isomorphic graphs either both belong to the class, or both do not belong to it.[1] Equivalently, a graph property may be formalized using the indicator function of the class, a function from graphs to Boolean values that is true for graphs in the class and false otherwise; again, any two isomorphic graphs must have the same function value as each other. A graph invariant or graph parameter may similarly be formalized as a function from graphs to a broader class of values, such as integers, real numbers, sequences of numbers, or polynomials, that again has the same value for any two isomorphic graphs.[2]

Properties of properties

Many graph properties are well-behaved with respect to certain natural partial orders or preorders defined on graphs:

These definitions may be extended from properties to numerical invariants of graphs: a graph invariant is hereditary, monotone, or minor-closed if the function formalizing the invariant forms a monotonic function from the corresponding partial order on graphs to the real numbers.

Additionally, graph invariants have been studied with respect to their behavior with regard to disjoint unions of graphs:

In addition, graph properties can be classified according to the type of graph they describe: whether the graph is undirected or directed, whether the property applies to multigraphs, etc.[1]

Values of invariants

The target set of a function that defines a graph invariant may be one of:

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 (the problem of graph canonization) 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.

Examples

Properties

Integer invariants

Real number invariants

Sequences and polynomials

See also

References

  1. 1 2 3 4 5 6 7 8 9 Lovász, László (2012), "4.1 Graph parameters and graph properties", Large Networks and Graph Limits, Colloquium Publications 60, American Mathematical Society, pp. 41–42.
  2. Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "3.10 Graph Parameters", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Springer, pp. 54–56, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.