graph property

Uses your system voice; voice and rate in settings.

Q722659Snapshot

≈ 6 min read

Names in other languages

  • Portuguêspropriedade de um grafo
  • capropietat de graf
  • etGraafi invariant
  • Magyargráftulajdonság
  • Русскийинвариант графа
  • УкраїнськаІнваріант графа
  • Englishgraph property
  • eoeco de grafo

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

and being connected, and with order 6, size 7, diameter 3, girth 3, vertex connectivity 1, and degree sequence 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.

and being connected, and with order 6, size 7, diameter 3, girth 3, vertex connectivity 1, and degree sequence 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 with the property that any two isomorphic graphs either both belong to the class, or both do not belong to it. 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.

Properties of properties

Many graph properties are well-behaved with respect to certain natural partial orders or preorders defined on graphs: A graph property P is hereditary if every induced subgraph of a graph with property P also has property P. For instance, being a perfect graph or being a chordal graph are hereditary properties. A graph property is monotone if every subgraph of a graph with property P also has property P. For instance, being a bipartite graph or being a triangle-free graph is monotone. Every monotone property is hereditary, but not necessarily vice versa; for instance, subgraphs of chordal graphs are not necessarily chordal, so being a chordal graph is not monotone. A graph property is minor-closed if every graph minor of a graph with property P also has property P. For instance, being a planar graph is minor-closed. Every minor-closed property is monotone, but not necessarily vice versa; for instance, minors of triangle-free graphs are not necessarily themselves triangle-free. 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: A graph invariant is additive if, for all two graphs G and H, the value of the invariant on the disjoint union of G and H is the sum of the values on G and on H. For instance, the number of vertices is additive. A graph invariant is multiplicative if, for all two graphs G and H, the value of the invariant on the disjoint union of G and H is the product of the values on G and on H. For instance, the Hosoya index (number of matchings) is multiplicative. A graph invariant is maxing if, for all two graphs G and H, the value of the invariant on the disjoint union of G and H is the maximum of the values on G and on H. For instance, the chromatic number is maxing. 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.

Values of invariants

The target set of a function that defines a graph invariant may be one of: A truth-value, true or false, for the indicator function of a graph property. An integer, such as the number of vertices or chromatic number of a graph. A real number, such as the fractional chromatic number of a graph. A sequence of integers, such as the degree sequence of a graph. A polynomial, such as the Tutte polynomial of a graph.

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 an efficiently computable such 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

Connected graphs Bipartite graphs Planar graphs Triangle-free graphs Perfect graphs Eulerian graphs Hamiltonian graphs

Integer invariants

Order, the number of vertices Size, the number of edges Number of connected components Circuit rank, a linear combination of the numbers of edges, vertices, and components diameter, the longest of the shortest path lengths between pairs of vertices girth, the length of the shortest cycle Vertex connectivity, the smallest number of vertices whose removal disconnects the graph Edge connectivity, the smallest number of edges whose removal disconnects the graph Chromatic number, the smallest number of colors for the vertices in a proper coloring Chromatic index, the smallest number of colors for the edges in a proper edge coloring Choosability (or list chromatic number), the least number k such that G is k-choosable Independence number, the largest size of an independent set of vertices Clique number, the largest order of a complete subgraph Arboricity Graph genus Pagenumber Hosoya index Wiener index Colin de Verdière graph invariant Boxicity

Real number invariants

Clustering coefficient Betweenness centrality Fractional chromatic number Algebraic connectivity Isoperimetric number Estrada index Strength

See also

Hereditary property Logic of graphs, one of several formal languages used to specify graph properties Topological index, a closely related concept in chemical graph theory List of integer invariants

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375953787 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot graph-property-082806-aefbadafba9a80d1 · hash aefbadafba9a80d16eedf322d90f7d66a935f6203babbd8c70c03ae52cfe6181 · captured 1789951729.0 · version history

Cite this page as: encyclopegia.org, “graph property”, snapshot graph-property-082806-aefbadafba9a80d1. https://encyclopegia.org/a/graph-property

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.