A lower bound on the order of regular graphs with given girth pair

The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 ( 1 ), 209–218]. A (δ, g)‐cage is a smallest δ‐regular graph with girth g. For all δ ≥ 3 and odd girth g ≥ 5, Harary and Kovács conjectured the existence of a (δ,g)‐cage that contains a cycle of length g + 1. In the main theorem of this article we present a lower bound on the order of a δ‐regular graph with odd girth g ≥ 5 and even girth h ≥ g + 3. We use this bound to show that every (δ,g)‐cage with δ ≥ 3 and g ∈ {5,7} contains a cycle of length g + 1, a result that can be seen as an extension of the aforementioned conjecture by Harary and Kovács for these values of δ, g. Moreover, for every odd g ≥ 5, we prove that the even girth of all (δ,g)‐cages with δ large enough is at most (3g ? 3)/2. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 153–163, 2007     

Triplets and Hexagons

Two combinatorial methods for constructing a family of symmetric trivalent graphs are presented in this paper. Each family of graphs contains a member for every odd prime numberp. It is proved that in one of the families the girth is unbounded as a function ofp; the other family contains the smallest known trivalent graphs of girth 18 and 19.     

Connectivity of graphs with given girth pair

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) is called the girth pair of the graph. In this paper we prove that a graph with girth pair (g,h) such that g is odd and h?g+3 is even has high (vertex-)connectivity if its diameter is at most h-3. The edge version of all results is also studied.     

Small vertex‐transitive and Cayley graphs of girth six and given degree: an algebraic approach

We examine the existing constructions of the smallest known vertex‐transitive graphs of a given degree and girth 6. It turns out that most of these graphs can be described in terms of regular lifts of suitable quotient graphs. A further outcome of our analysis is a precise identification of which of these graphs are Cayley. We also investigate higher level of transitivity of the smallest known vertex‐transitive graphs of a given degree and girth 6 and relate their constructions to near‐difference sets. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:265‐284, 2011     

Decomposing a planar graph with girth at least 8 into a forest and a matching

W. He et al. showed that a planar graph of girth at least 11 can be decomposed into a forest and a matching. A. Bass et al. proved the same statement for planar graphs of girth at least 10. Recently, O.V. Borodin et al. improved the bound on the girth to 9. In this paper, we further improve the bound on the girth to 8. This bound is the best possible in the sense that there are planar graphs with girth 7 that cannot be decomposed into a forest and a matching.     

(2 + ϵ)‐Coloring of planar graphs with large odd‐girth

The odd‐girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function ƒ(ϵ) for each ϵ : 0 < ϵ < 1 such that, if the odd‐girth of a planar graph G is at least ƒ(ϵ), then G is (2 + ϵ)‐colorable. Note that the function ƒ(ϵ) is independent of the graph G and ϵ → 0 if and only if ƒ(ϵ) → ∞. A key lemma, called the folding lemma, is proved that provides a reduction method, which maintains the odd‐girth of planar graphs. This lemma is expected to have applications in related problems. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 109–119, 2000     

3-list-coloring planar graphs of girth 4

In Thomassen (1995) [4], Thomassen proved that planar graphs of girth at least 5 are 3-choosable. In Li (2009) [3], Li improved Thomassen’s result by proving that planar graphs of girth 4 with no 4-cycle sharing a vertex with another 4- or 5-cycle are 3-choosable. In this paper, we prove that planar graphs of girth 4 with no 4-cycle sharing an edge with another 4- or 5-cycle are 3-choosable. It is clear that our result strengthens Li’s result.     

The face pair of planar graphs

Harary and Kovacs [Smallest graphs with given girth pair, Caribbean J. Math. 1 (1982) 24-26] have introduced a generalization of the standard cage question—r-regular graphs with given odd and even girth pair. The pair (ω,ε) is the girth pair of graph G if the shortest odd and even cycles of G have lengths ω and ε, respectively, and denote the number of vertices in the (r,ω,ε)-cage by f(r,ω,ε). Campbell [On the face pair of cubic planar graph, Utilitas Math. 48 (1995) 145-153] looks only at planar graphs and considers odd and even faces rather than odd and even cycles. He has shown that f(3,ω,4)=2ω and the bounds for the left cases. In this paper, we show the values of f(r,ω,ε) for the left cases where (r,ω,ε)∈{(3,3,ε),(4,3,ε),(5,3,ε), (3,5,ε)}.     

Partitions of Graphs into Cographs

Cographs from the minimal family of graphs containing K₁ which are closed with respect to complements and unions. We discuss vertex partitions of graphs into the smallest number of cographs, where the partition is as small as possible. We shall call the order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show both bounds are sharp, for graphs with arbitrarily high girth. This provides an alternative proof to a result in [3]; there exist triangle-free graphs with arbitrarily large c-chromatic numbers. We show that any planar graph with girth at least 11 has a c-chromatic number of at most two. We close with several remarks on computational complexity. In particular, we show that computing the c-chromatic number is NP-complete for planar graphs.     

Planar Hypohamiltonian Graphs on 40 Vertices

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer‐aided generation of certain families of planar graphs with girth 4 and a fixed number of 4‐faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.     

Cubic vertex-transitive graphs of girth six

In this paper, a complete classification of finite simple cubic vertex-transitive graphs of girth 6 is obtained. It is proved that every such graph, with the exception of the Desargues graph on 20 vertices, is either a skeleton of a hexagonal tiling of the torus, the skeleton of the truncation of an arc-transitive triangulation of a closed hyperbolic surface, or the truncation of a 6-regular graph with respect to an arc-transitive dihedral scheme. Cubic vertex-transitive graphs of girth larger than 6 are also discussed.     

Remarks on the bondage number of planar graphs

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. In 1998, J.E. Dunbar, T.W. Haynes, U. Teschner, and L. Volkmann posed the conjecture b(G)Δ(G)+1 for every nontrivial connected planar graph G. Two years later, L. Kang and J. Yuan proved b(G)8 for every connected planar graph G, and therefore, they confirmed the conjecture for Δ(G)7. In this paper we show that this conjecture is valid for all connected planar graphs of girth g(G)4 and maximum degree Δ(G)5 as well as for all not 3-regular graphs of girth g(G)5. Some further related results and open problems are also presented.     

Super cyclically edge-connected vertex-transitive graphs of girth at least 5

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super-λc, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In [Zhang, Z., Wang, B.: Super cyclically edge-connected transitive graphs. J. Combin. Optim., 22, 549-562 (2011)], it is proved that a connected vertex-transitive graph is super-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k (k≥4)-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k (k≥4)-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.     

The list chromatic numbers of some planar graphs

In this paper, the choosability of outerplanar graphs, 1-tree and strong 1-outerplanargraphs have been described completely. A precise upper bound of the list chromatic number of 1-outerplanar graphs is given, and that every 1-outerplanar graph with girth at least 4 is 3-choosable is proved.     

Unsolved Problems on Distance in Graphs

The distance between a pair of nodes of a graph G is the length of a shortest path connecting them. The eccentricity of a node v is the greatest distance between v and another node. The radius and diameter of a graph are, respectively, the smallest and largest eccentricities among its nodes. The status of v is the sum of the distances from v to all other nodes. We shall discuss various conjectures and unsolved problems concerning distance concepts in graphs. These problems involve radius, diameter, and status, as well as other distance concepts such as distance sequences, domination, distance in digraphs, and convexity.     

Chromatic number of sparse colored mixed planar graphs

A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph G is defined as the smallest order of a colored mixed graph H such that there exists a (arc-color preserving) homomorphism from G to H. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.     

Bigeodetic graphs

Bigeodetic graphs, a generalization of geodetic and interval-regular graphs, are defined as graphs in which each pair of vertices has at most two paths of minimum length between them. The block cut-vertex incidence pattern of bigeodetic separable graphs are discussed. Two characterizations of bigeodetic graphs are given and some properties of these graphs are studied. Construction of planar bigeodetic blocks with given girth and diameter, and construction of hamiltonian and eulerian/nonhamiltonian and noneulerian, perfect bigeodetic blocks are discussed. The extremal bigeodetic graph of diameterd onp d + 1 vertices is constructed.On leave from A.M. Jain College, Madras University, Madras 600114, India     

Cages—a survey

We discuss the problem of finding smallest graphs of given girth g and valency v ((v, g)-cages). All known (v, g)-cages are given. Different variations of the cage problem are also discussed.     

Distance-regular graphs and (s,c, a,k)-graphs

A diameter-bound theorem for a class of distance-regular graphs which includes all those with even girth is presented. A new class of graphs, called (s, c, a, k)-graphs, is introduced, which are conjectured to contain enough of the local structure of finite distance-regular graphs for them all to be finite. It is proved that they are finite and a bound on the diameter is given in the case a ≤ c.