Graph, numerical characteristics of a

Functions specified on the set of graphs and taking values in a certain set of numbers. A number of such characteristics, with their most common notations, are given below. The simplest numerical characteristics of a graph are the number of vertices and the number of edges (arcs) of a graph $ G $. The cyclomatic number $ \nu ( G) $ of $ G $ is the smallest number of edges whose removal yields a graph without cycles:

$$ \nu ( G) = m - n + k, $$

where $ m $ is the number of edges, $ n $ is the number of vertices and $ k $ is the number of connected components of $ G $. The vertex-connectivity number $ \kappa ( G) $( the edge-connectivity number $ \lambda ( G) $) is the smallest number of vertices (edges) of $ G $ whose removal yields a non-connected graph or a trivial graph (i.e. a graph consisting of a single vertex). The density $ \phi ( G) $ is the largest number of vertices in a complete subgraph of $ G $; the independence number, or the number of internal stability, $ \epsilon ( G) $ is the largest number of pairwise non-adjacent vertices of $ G $( and the pairwise non-adjacent vertices of $ G $ form an internally stable set). The chromatic number $ \chi ( G) $( edge chromatic number $ \chi ^ \prime ( G) $) is the smallest number of colours required to colour the vertices (edges) of $ G $ so that any adjacent vertices (edges) are coloured with different colours (see also Graph colouring). The number of external stability $ \beta ( G) $ is the smallest number of vertices in a subset $ W $ of the set of vertices of $ G $ such that any vertex not belonging to $ W $ is adjacent to at least one vertex of $ W $. The aborescence $ \Upsilon ( G) $ is the smallest number of spanning forests of $ G $ which do not intersect at the edges, and whose union yields $ G $. The coarseness $ \xi ( G) $ is the largest number of non-planar subgraphs of $ G $ which do not intersect at the edges and whose union is $ G $. The thickness $ \theta ( G) $ is the smallest number of planar subgraphs whose union yields $ G $. The crossing number is the smallest number of pairwise intersections of the edges of $ G $ when placed on a plane. The genus $ \gamma ( G) $ of $ G $ is the smallest genus of the two-dimensional orientable surface on which $ G $ can be placed without its edges intersecting (cf. Graph imbedding).

Certain numerical characteristics concern the number of subgraphs of the given graph of a certain type — e.g. the number of spanning trees, the number of Hamilton cycles, etc. There are characteristics which depend on a parameter $ f _ {k} ( G) $( e.g. the number of complete subgraphs with $ k $ vertices), and the totality of these characteristics can be specified by the polynomial $ \sum _ {k} f _ {k} ( G) x ^ {k} $— the analogue of the generating function. Many such polynomials can be found recursively by the application of operations on graphs — removal of a vertex or of an edge, contraction of an edge, etc. In solving graph-theoretic problems it is often necessary to study relationships between different numerical characteristics. These attain their extremal values on certain sets, and such values can often be used in describing the graphs on which they are attained. In such a case finding the extremal values is reduced to the study of such graphs. In studying the graphs for which a characteristic under consideration assumes a given value, it may be useful to study the properties of critical graphs (cf. Graph, extremal).

References

[1]	A.A. Zykov, "The theory of finite graphs" , 1 , Novosibirsk (1969) (In Russian)
[2]	V.P. Kozyrev, "Graph theory" J. Soviet Math. , 2 (1974) pp. 489–519 Itogi Nauk. i Tekhn. Ser. Teor. Veroyatn. Mat. Stat. Teoret. Kibernet. , 10 (1972) pp. 25–75
[3]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9

Comments

Numerical characteristics of graphs are also called graph parameters. Isomorphic graphs have the same values for the parameters. A set of parameters is complete if there is only one graph (up to isomorphism) for any given choice of values for the parameters in the set. The problem of finding a complete set of parameters is still unsolved.

References

[a1]	R.J. Wilson, "Introduction to graph theory" , Longman (1985)