Graph circuit

An edge progression containing all the vertices or edges of a graph with certain properties. The best-known graph circuits are Euler and Hamilton chains and cycles. An edge progression (a closed edge progression) is an Euler chain (Euler cycle) if it contains all the edges of the graph and passes through each edge once. There exists an effective criterion for the existence of Euler cycles (Euler's theorem): A connected graph has an Euler cycle if and only if each of its vertices (except two) has even degree.

An edge progression (closed edge progression) is called a Hamilton chain (Hamilton cycle) if it contains all the vertices of the graph and if it passes through each of them once. Several conditions sufficient for the existence of Hamilton cycles are known, such as: The graph has no loops or multiple edges and, for any two of its non-adjacent edges, the sum of their degrees is not less than the number of vertices in the graph; the graph is planar and quadruply-connected; the graph has no loops or multiple edges, and the number $ n $ of its vertices and $ m $ of its edges satisfy the conditions $ n \geq 3 $ and $ m \geq ( n ^ {2} - 3n + 6)/2 $. A graph is said to be Hamiltonian (Eulerian) if it has a Hamilton (Euler) cycle. A graph is said to be Hamilton-connected if any two of its vertices are connected by a Hamilton chain, and is said to be $ k $- Hamiltonian if any simple chain of length $ k $ forms part of some Hamilton cycle. The well-known "Travelling Salesman Problem" is to find in a graph with edges labeled with non-negative numbers (lengths of edges) a Hamilton cycle with the smallest sum of edge lengths. This problem and other problems of graph circuits have various technological and economic applications.

References

[1]	F. Harary, "Graph theory" , Addison-Wesley (1969)
[2]	A.A. Zykov, "The theory of finite graphs" , 1 , Novosibirsk (1969) (In Russian)

Comments

Finding a good characterization of Hamiltonian graphs and a good algorithm for finding a Hamilton cycle are difficult open problems. The latter is a known $ {\mathcal N} {\mathcal P} $-complete problem. A recent survey on Eulerian graphs is [a1] and one on Hamiltonian graphs is [a2].

An edge sequence (edge progression or walk) is a sequence of alternating vertices and edges $ v _ {0} e _ {0} v _ {1} \dots e _ {n - 1 } v _ {n} $ such that $ e _ {i} $ is an edge between $ v _ {i - 1 } $ and $ v _ {i} $( and in case one is dealing with an oriental graph $ e _ {i} $ should go from $ v _ {i - 1 } $ to $ v _ {i} $). An edge sequence with all edges in it distinct is called a path. A path with all vertices distinct (except possibly $ v _ {0} = v _ {n} $) is called a chain. A chain with $ v _ {0} = v _ {n} $ is a circuit.

References

[a1]	L. Lesniak, O.R. Oellerman, "An eulerian exposition" J. Graph Theory , 10 (1986) pp. 277–297
[a2]	J.C. Bermond, "Hamiltonian graphs" L.W. Beineke (ed.) R.J. Wilson (ed.) , Selected Topics in Graph Theory , Acad. Press pp. Chapt. 6
[a3]	H.-J. Walther, "Ten applications of graph theory" , Reidel (1984)
[a4]	W.K. Chen, "Applied graph theory" , North-Holland (1971)