Girth (graph theory)

The girth in graph theory is the length of the smallest cycle contained in a given graph ^[1] . If a graph does not contain cycles (that is, it is an acyclic graph), its girth is by definition equal to infinity ^[2] . For example, a 4-cycle (square) has a girth of 4. A square lattice also has a girth of 4, and a triangular grid has a girth of 3. A graph with a girth of four or more has no triangles .

Content

Cells

Cubic graphs (all vertices have degree three) with as little girth as possible $g$ ${\ displaystyle g}$ known as $g$ ${\ displaystyle g}$ - cells (or how (3, $g$ ${\ displaystyle g}$ ) -cells). The Petersen graph is the only 5-cell (the smallest cubic graph with girth of 5), the Howwood graph is the only 6-cell, the McGee graph is the only 7-cell, and the Tutt – Coxeter graph is the only 8-cell ^[3] . There may be several (graphs) cells for a given girth. For example, there are three nonisomorphic 10-cells, each with 70 vertices — the , Earl of Harris, and Earl of Harris – Wong .

Count Petersen has a girth of 5
Earl of Howwood has a girth of 6
Count McGee has a girth of 7
Count Tatt - Coxeter ( 8-cell Tatt ) has a girth of 8

Count and coloring

For any positive integer $k$ ${\ displaystyle k}$ there is a graph $G$ ${\ displaystyle G}$ with girth $g(G)\geq k$ ${\ displaystyle g (G) \ geq k}$ and chromatic number $\chi (G)\geq k$ ${\ displaystyle \ chi (G) \ geq k}$ . For example, the Grech graph is a graph without triangles and has a chromatic number of 4, and repeated repetition of the Mytselsky construction used to create the Grech graph forms graphs without triangles with an arbitrarily large chromatic number. Paul Erdös proved this theorem using the probabilistic method ^[4] .

Plan of evidence . We call cycles no longer than $k$ ${\ displaystyle k}$ short, and sets with $|G|/k$ ${\ displaystyle | G | / k}$ and more peaks - large. To prove the theorem, it suffices to find the graph $G$ ${\ displaystyle G}$ without short cycles and large independent sets of vertices. Then the sets of colors in the coloring will not be large, and, as a result, for coloring $k$ ${\ displaystyle k}$ colors.

To find such a graph, we fix the probability of choice $p$ ${\ displaystyle p}$ equal $n^{\epsilon -1}$ ${\ displaystyle n ^ {\ epsilon -1}}$ . At small $\epsilon$ ${\ displaystyle \ epsilon}$ at $G$ ${\ displaystyle G}$ only a small number of short cycles occur. If now we remove the vertex from each such cycle, the resulting graph $H$ ${\ displaystyle H}$ will not have short cycles, and its independence number will be no less than that of the graph $G$ ${\ displaystyle G}$ ^[1] .

Close Concepts

The odd girth and the even girth of the graph are the lengths of the smallest odd cycle and the even cycle, respectively.

The circumference of the graph is the length of the longest cycle, not the smallest.

Reflections on the length of the smallest nontrivial cycle can be considered as a generalization of 1-systole or greater systole in .

Notes

↑ ¹ ² Reingard Distel. Graph theory. - Novosibirsk: Publishing House of the Institute of Mathematics, 2002.
↑ Girth - Wolfram MathWorld.
↑ Andries E. Brouwer. Cages. Electronic appendix to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier 1989, Springer-Verlag).
↑ Paul Erdős. Graph theory and probability // Canadian Journal of Mathematics. - 1959.- T. 11 . - S. 34-38 . - DOI : 10.4153 / CJM-1959-003-9 .

[Diestel-1] ¹ ² Reingard Distel. Graph theory. - Novosibirsk: Publishing House of the Institute of Mathematics, 2002.

[2] Girth - Wolfram MathWorld.

[3] Andries E. Brouwer. Cages. Electronic appendix to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier 1989, Springer-Verlag).

[4] Paul Erdős. Graph theory and probability // Canadian Journal of Mathematics. - 1959.- T. 11 . - S. 34-38 . - DOI : 10.4153 / CJM-1959-003-9 .