Girth (graph theory)

Last updated

In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. [1] If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be infinity. [2] For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

Contents

Cages

A cubic graph (all vertices have degree three) of girth g that is as small as possible is known as a g-cage (or as a (3,g)-cage). The Petersen graph is the unique 5-cage (it is the smallest cubic graph of girth 5), the Heawood graph is the unique 6-cage, the McGee graph is the unique 7-cage and the Tutte eight cage is the unique 8-cage. [3] There may exist multiple cages for a given girth. For instance there are three nonisomorphic 10-cages, each with 70 vertices: the Balaban 10-cage, the Harries graph and the Harries–Wong graph.

Girth and graph coloring

For any positive integers g and χ, there exists a graph with girth at least g and chromatic number at least χ; for instance, the Grötzsch graph is triangle-free and has chromatic number 4, and repeating the Mycielskian construction used to form the Grötzsch graph produces triangle-free graphs of arbitrarily large chromatic number. Paul Erdős was the first to prove the general result, using the probabilistic method. [4] More precisely, he showed that a random graph on n vertices, formed by choosing independently whether to include each edge with probability n(1  g)/g, has, with probability tending to 1 as n goes to infinity, at most n/2 cycles of length g or less, but has no independent set of size n/2k. Therefore, removing one vertex from each short cycle leaves a smaller graph with girth greater than g, in which each color class of a coloring must be small and which therefore requires at least k colors in any coloring.

Explicit, though large, graphs with high girth and chromatic number can be constructed as certain Cayley graphs of linear groups over finite fields. [5] These remarkable Ramanujan graphs also have large expansion coefficient.

The odd girth and even girth of a graph are the lengths of a shortest odd cycle and shortest even cycle respectively.

The circumference of a graph is the length of the longest (simple) cycle, rather than the shortest.

Thought of as the least length of a non-trivial cycle, the girth admits natural generalisations as the 1-systole or higher systoles in systolic geometry.

Girth is the dual concept to edge connectivity, in the sense that the girth of a planar graph is the edge connectivity of its dual graph, and vice versa. These concepts are unified in matroid theory by the girth of a matroid, the size of the smallest dependent set in the matroid. For a graphic matroid, the matroid girth equals the girth of the underlying graph, while for a co-graphic matroid it equals the edge connectivity. [6]

Related Research Articles

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Graph coloring

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 of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Extremal graph theory

Extremal graph theory is a branch of mathematics that studies how global properties of a graph influence local substructure. It encompasses a vast number of results that describe how do certain graph properties - number of vertices (size), number of edges, edge density, chromatic number, and girth, for example - guarantee the existence of certain local substructures.

Heawood graph

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

Graph property

In graph theory, 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 of the graph.

Wheel graph

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as the 1-skeleton of an (n-1)-gonal pyramid. Some authors write Wn to denote a wheel graph with n vertices ; other authors instead use Wn to denote a wheel graph with n+1 vertices, which is formed by connecting a single vertex to all vertices of a cycle of length n. In the rest of this article we use the former notation.

Dual graph

In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

Hoffman–Singleton graph

In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest-order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.

In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound

In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

Coxeter graph

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.

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 girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of Jan Mycielski (1955). The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number.

Grötzsch graph

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch.

Cage (graph theory)

In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.

Chvátal graph

In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal (1970).

McGee graph

In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3-regular graph with 24 vertices and 36 edges.

Brinkmann graph

In the mathematical field of graph theory, the Brinkmann graph is a 4-regular graph with 21 vertices and 42 edges discovered by Gunnar Brinkmann in 1992. It was first published by Brinkmann and Meringer in 1997.

Tutte 12-cage

In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte.

In matroid theory, a mathematical discipline, the girth of a matroid is the size of its smallest circuit or dependent set. The cogirth of a matroid is the girth of its dual matroid. Matroid girth generalizes the notion of the shortest cycle in a graph, the edge connectivity of a graph, Hall sets in bipartite graphs, even sets in families of sets, and general position of point sets. It is hard to compute, but fixed-parameter tractable for linear matroids when parameterized both by the matroid rank and the field size of a linear representation.

References

  1. R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
  2. Weisstein, Eric W., "Girth", MathWorld
  3. Brouwer, Andries E., Cages . Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
  4. Erdős, Paul (1959), "Graph theory and probability", Canadian Journal of Mathematics, 11: 34–38, doi:10.4153/CJM-1959-003-9 .
  5. Davidoff, Giuliana; Sarnak, Peter; Valette, Alain (2003), Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, 55, Cambridge University Press, Cambridge, doi:10.1017/CBO9780511615825, ISBN   0-521-82426-5, MR   1989434
  6. Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics, 155 (18): 2456–2470, doi:10.1016/j.dam.2007.06.015, MR   2365057 .