graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a graph property or graph invariant is a property of

graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discre ...

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

isomorphism In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

s 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 In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

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 In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , then the indicator functio ...

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 number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...

s, sequences of numbers, or

polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...

s, 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 order In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable ...

s or

preorder In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive relation, reflexive and Transitive relation, transitive. The name is meant to suggest that preorders are ''almost'' partial orders, ...

s defined on graphs: *A graph property ''P'' is ''

hereditary Heredity, also called inheritance or biological inheritance, is the passing on of traits from parents to their offspring; either through asexual reproduction or sexual reproduction, the offspring cells or organisms acquire the genetic inform ...

'' if every

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

of a graph with property ''P'' also has property ''P''. For instance, being a

perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

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 In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

or being a

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

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 In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

of a graph with property ''P'' also has property ''P''. For instance, being a

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

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 In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of or ...

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 union In mathematics, the disjoint union (or discriminated union) A \sqcup B of the sets and is the set formed from the elements of and labelled (indexed) with the name of the set from which they come. So, an element belonging to both and appe ...

s 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 In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

is maxing. In addition, graph properties can be classified according to the type of graph they describe: whether the graph is

undirected In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

directed Direct may refer to: Mathematics * Directed set, in order theory * Direct limit of (pre), sheaves * Direct sum of modules, a construction in abstract algebra which combines several vector spaces Computing * Direct access (disambiguation), a ...

, whether the property applies to

multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mor ...

s, 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

, such as the fractional chromatic number of a graph. *A sequence of integers, such as the degree sequence of a graph. *A

, 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 In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...

, 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 The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational c ...

. However, even polynomial-valued invariants such as the chromatic polynomial are not usually complete. The claw graph and the

path graph In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...

on 4 vertices both have the same chromatic polynomial, for example.

Examples

Properties

Connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...

s *

Bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

s *

Planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

s *

Triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

s *

Perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

s * Eulerian graphs *

Hamiltonian graph In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each verte ...

Integer invariants

Order Order, ORDER or Orders may refer to: * A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica * Categorization, the process in which ideas and objects are recognized, differentiated, and understood ...

, the number of vertices *

Size Size in general is the Magnitude (mathematics), magnitude or dimensions of a thing. More specifically, ''geometrical size'' (or ''spatial size'') can refer to three geometrical measures: length, area, or volume. Length can be generalized ...

, the number of edges * Number of connected components * Circuit rank, a linear combination of the numbers of edges, vertices, and components *

diameter In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

, the longest of the shortest

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desir ...

lengths between pairs of vertices *

girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * 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 In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

, the smallest number of colors for the vertices in a proper coloring *

Chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge colorin ...

, the smallest number of colors for the edges in a proper edge coloring *

Choosability In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each Vertex (graph theory), vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vadim G. Vizing ...

(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 In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of t ...

, the largest order of a complete subgraph * Arboricity * Graph genus * Pagenumber * Hosoya index * Wiener index * Colin de Verdière graph invariant *

Boxicity In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there mus ...

Real number invariants

Clustering coefficient In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups ...

Betweenness centrality In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices, that is, there exists at leas ...

* Fractional chromatic number * Algebraic connectivity * Isoperimetric number * Estrada index *

Strength Strength may refer to: Personal trait *Physical strength, as in people or animals *Character strengths like those listed in the Values in Action Inventory *The exercise of willpower Physics * Mechanical strength, the ability to withstand ...

Sequences and polynomials

* Degree sequence * Graph spectrum *

Characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...

of the

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...

* 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

Edge partition

* (a, b)-decomposition for any natural a,b

External links

List of integer invariants

References

{{DEFAULTSORT:Graph Property * Graph theory