Namespaces
Variants
Actions

Difference between revisions of "Graph, numerical characteristics of a"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g0449601.png" />. The cyclomatic number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g0449602.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g0449603.png" /> is the smallest number of edges whose removal yields a graph without cycles:
+
<!--
 +
g0449601.png
 +
$#A+1 = 39 n = 0
 +
$#C+1 = 39 : ~/encyclopedia/old_files/data/G044/G.0404960 Graph, numerical characteristics of a
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g0449604.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g0449605.png" /> is the number of edges, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g0449606.png" /> is the number of vertices and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g0449607.png" /> is the number of connected components of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g0449608.png" />. The vertex-connectivity number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g0449609.png" /> (the edge-connectivity number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496010.png" />) is the smallest number of vertices (edges) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496011.png" /> whose removal yields a non-connected graph or a trivial graph (i.e. a graph consisting of a single vertex). The density <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496012.png" /> is the largest number of vertices in a complete subgraph of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496013.png" />; the independence number, or the number of internal stability, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496014.png" /> is the largest number of pairwise non-adjacent vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496015.png" /> (and the pairwise non-adjacent vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496016.png" /> form an internally stable set). The chromatic number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496017.png" /> (edge chromatic number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496018.png" />) is the smallest number of colours required to colour the vertices (edges) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496019.png" /> so that any adjacent vertices (edges) are coloured with different colours (see also [[Graph colouring|Graph colouring]]). The number of external stability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496020.png" /> is the smallest number of vertices in a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496021.png" /> of the set of vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496022.png" /> such that any vertex not belonging to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496023.png" /> is adjacent to at least one vertex of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496024.png" />. The aborescence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496025.png" /> is the smallest number of spanning forests of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496026.png" /> which do not intersect at the edges, and whose union yields <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496027.png" />. The coarseness <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496028.png" /> is the largest number of non-planar subgraphs of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496029.png" /> which do not intersect at the edges and whose union is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496030.png" />. The thickness <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496031.png" /> is the smallest number of planar subgraphs whose union yields <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496032.png" />. The crossing number is the smallest number of pairwise intersections of the edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496033.png" /> when placed on a plane. The genus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496034.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496035.png" /> is the smallest genus of the two-dimensional orientable surface on which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496036.png" /> can be placed without its edges intersecting (cf. [[Graph imbedding|Graph imbedding]]).
+
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:
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496037.png" /> (e.g. the number of complete subgraphs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496038.png" /> vertices), and the totality of these characteristics can be specified by the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044960/g04496039.png" /> — 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|Graph, extremal]]).
+
$$
 +
\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|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|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|Graph, extremal]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Zykov,  "The theory of finite graphs" , '''1''' , Novosibirsk  (1969)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Zykov,  "The theory of finite graphs" , '''1''' , Novosibirsk  (1969)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Revision as of 19:42, 5 June 2020


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)
How to Cite This Entry:
Graph, numerical characteristics of a. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph,_numerical_characteristics_of_a&oldid=16719
This article was adapted from an original article by V.P. Kozyrev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article