graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, 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 Drawing is a visual art that uses an instrument to mark paper or another two-dimensional surface. The instruments used to make a drawing are pencils, crayons, pens with inks, brushes with paints, or combinations of these, and in more modern times ...

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 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 them. The word i ...

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 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 , one has \mathbf_(x)=1 if x ...

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 measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...

s, sequences of numbers, or

polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...

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 partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...

s or

preorder In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...

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 infor ...

'' if every

induced subgraph In the mathematical field of 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. Definit ...

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 in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph ( clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is per ...

or being a

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...

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 mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

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 and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only i ...

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 that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

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 ord ...

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, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ...

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 special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

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, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ...

directed Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...

, 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 mo ...

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) ...

, 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 In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph ''G''. A canonical form is a labeled graph Canon(''G'') that is isomorphic to ''G'', such that every graph that is isomorphic ...

) 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 comp ...

. 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 terminal ...

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 subgra ...

s *

Bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

s *

Planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

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 in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph ( clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is per ...

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 vertex ...

Integer invariants

Order Order, ORDER or Orders may refer to: * Categorization, the process in which ideas and objects are recognized, differentiated, and understood * Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...

, 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 linear dimensions (length, width, height, diameter, perimeter), area, or volume ...

, the number of edges * Number of connected components *

Circuit rank In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycle (graph theory), cycles, making ...

, 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 center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...

, 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 In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeration ...

, the smallest number of edges whose removal disconnects the graph *

Chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

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

Chromatic index In graph theory, an edge coloring of a 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 coloring of a graph by the colors red, blue ...

, 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 can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Tayl ...

(or list chromatic number), the least number k such that G is k-choosable *

Independence number Independence is a condition of a person, nation, country, or Sovereign state, state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independ ...

, the largest size of an independent set of vertices * Clique number, the largest order of a complete subgraph *

Arboricity The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem pro ...

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

* Pagenumber * Hosoya index * Wiener index * Colin de Verdière graph invariant * Boxicity

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 (or "betweeness 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 suc ...

* Fractional chromatic number *

Algebraic connectivity The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after Miroslav Fiedler) of a graph ''G'' is the second-smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of ''G''. This eigenvalue i ...

* Isoperimetric number * Estrada index * Strength

Sequences and polynomials

* Degree sequence *

Graph spectrum In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. ...

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. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

* 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

References

{{DEFAULTSORT:Graph Property * Graph theory