Graph property

From Wikipedia for FEVERv2
(Redirected from Graph invariant)
Jump to navigation Jump to search

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. Graph property_sentence_0

Definitions Graph property_section_0

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. Graph property_sentence_1

In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph. Graph property_sentence_2

Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. Graph property_sentence_3

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". Graph property_sentence_4

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. Graph property_sentence_5

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. Graph property_sentence_6

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. Graph property_sentence_7

Properties of properties Graph property_section_1

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

Graph property_unordered_list_0

  • 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.Graph property_item_0_0
  • 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.Graph property_item_0_1
  • 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.Graph property_item_0_2

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. Graph property_sentence_9

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

Graph property_unordered_list_1

  • 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.Graph property_item_1_3
  • 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.Graph property_item_1_4
  • 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.Graph property_item_1_5

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. Graph property_sentence_11

Values of invariants Graph property_section_2

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

Graph property_unordered_list_2

  • A truth-value, true or false, for the indicator function of a graph property.Graph property_item_2_6
  • An integer, such as the number of vertices or chromatic number of a graph.Graph property_item_2_7
  • A real number, such as the fractional chromatic number of a graph.Graph property_item_2_8
  • A sequence of integers, such as the degree sequence of a graph.Graph property_item_2_9
  • A polynomial, such as the Tutte polynomial of a graph.Graph property_item_2_10

Graph invariants and graph isomorphism Graph property_section_3

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. Graph property_sentence_13

Two graphs with the same invariants may or may not be isomorphic, however. Graph property_sentence_14

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. Graph property_sentence_15

However, even polynomial-valued invariants such as the chromatic polynomial are not usually complete. Graph property_sentence_16

The claw graph and the path graph on 4 vertices both have the same chromatic polynomial, for example. Graph property_sentence_17

Examples Graph property_section_4

Properties Graph property_section_5

Graph property_unordered_list_3

Integer invariants Graph property_section_6

Graph property_unordered_list_4

  • Order, the number of verticesGraph property_item_4_18
  • Size, the number of edgesGraph property_item_4_19
  • Number of connected componentsGraph property_item_4_20
  • Circuit rank, a linear combination of the numbers of edges, vertices, and componentsGraph property_item_4_21
  • diameter, the longest of the shortest path lengths between pairs of verticesGraph property_item_4_22
  • girth, the length of the shortest cycleGraph property_item_4_23
  • Vertex connectivity, the smallest number of vertices whose removal disconnects the graphGraph property_item_4_24
  • Edge connectivity, the smallest number of edges whose removal disconnects the graphGraph property_item_4_25
  • Chromatic number, the smallest number of colors for the vertices in a proper coloringGraph property_item_4_26
  • Chromatic index, the smallest number of colors for the edges in a proper edge coloringGraph property_item_4_27
  • Choosability (or list chromatic number), the least number k such that G is k-choosableGraph property_item_4_28
  • Independence number, the largest size of an independent set of verticesGraph property_item_4_29
  • Clique number, the largest order of a complete subgraphGraph property_item_4_30
  • ArboricityGraph property_item_4_31
  • Graph genusGraph property_item_4_32
  • PagenumberGraph property_item_4_33
  • Hosoya indexGraph property_item_4_34
  • Wiener indexGraph property_item_4_35
  • Colin de Verdière graph invariantGraph property_item_4_36
  • BoxicityGraph property_item_4_37

Real number invariants Graph property_section_7

Graph property_unordered_list_5

Sequences and polynomials Graph property_section_8

See also Graph property_section_9

Graph property_unordered_list_6

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: property.