Article ID Journal Published Year Pages File Type
4651236 Discrete Mathematics 2007 8 Pages PDF
Abstract

Girth pairs were introduced by Harary and Kovács [Regular graphs with given girth pair, J. Graph Theory 7 (1983) 209–218]. The odd girth (even girth) of a graph is the length of a shortest odd (even) cycle. Let g denote the smaller of the odd and even girths, and let h   denote the larger. Then (g,h)(g,h) is called the girth pair of the graph. In this paper we prove that a graph with girth pair (g,h)(g,h) such that g   is odd and h⩾g+3h⩾g+3 is even has high (vertex-)connectivity if its diameter is at most h-3h-3. The edge version of all results is also studied.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , ,