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     

The maximum valency of regular graphs with given order and odd girth

The odd girth of a graph G is the length of a shortest odd cycle in G. Let d(n, g) denote the largest k such that there exists a k-regular graph of order n and odd girth g. It is shown that dn, g ≥ 2|n/g≥ if n ≥ 2g. As a consequence, we prove a conjecture of Pullman and Wormald, which says that there exists a 2j-regular graph of order n and odd girth g if and only if n ≥ gj, where g ≥ 5 is odd and j ≥ 2. A different variation of the problem is also discussed.     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

The forcing number of graphs with given girth

In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The forcing number, originally known as the zero forcing number, and denoted F (G), of G is the cardinality of a smallest forcing set of G. We study lower bounds on the forcing number in terms of its minimum degree and girth, where the girth g of a graph is the length of a shortest cycle in the graph. Let G be a graph with minimum degree δ ≥ 2 and girth g ≥ 3. Davila and Kenter [Theory and Applications of Graphs, Volume 2, Issue 2, Article 1, 2015] conjecture that F (G) ≥ δ + (δ ? 2)(g ? 3). This conjecture has recently been proven for g ≤ 6. The conjecture is also proven when the girth g ≥ 7 and the minimum degree is sufficiently large. In particular, it holds when g = 7 and δ ≥ 481, when g = 8 and δ ≥ 649, when g = 9 and δ ≥ 30, and when g = 10 and δ ≥ 34. In this paper, we prove the conjecture for g ∈ {7, 8, 9, 10} and for all values of δ ≥ 2.     

Retracts of box products with odd‐angulated factors

Let G be a connected graph with odd girth 2κ+1. Then G is a (2κ+1)‐angulated graph if every two vertices of G are connected by a path such that each edge of the path is in some (2κ+1)‐cycle. We prove that if G is (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+3, then any retract of the box (or Cartesian) product G□ H is S□T where S is a retract of G and T is a connected subgraph of H. A graph G is strongly (2κ+1)‐angulated if any two vertices of G are connected by a sequence of (2κ+1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+1, then any retract of G□ H is S□T where S is a retract of G and T is a connected subgraph of H or |V(S)|=1 and T is a retract of H. These two results improve theorems on weakly and strongly triangulated graphs by Nowakowski and Rival [Disc Math 70 ( 13 ), 169–184]. As a corollary, we get that the core of the box product of two strongly (2κ+1)‐angulated cores must be either one of the factors or the box product itself. Furthermore, if G is a strongly (2κ+1)‐angulated core, then either Gⁿ is a core for all positive integers n, or the core of Gⁿ is G for all positive integers n. In the latter case, G is homomorphically equivalent to a normal Cayley graph [Larose, Laviolette, Tardiff, European J Combin 19 ( 12 ), 867–881]. In particular, let G be a strongly (2κ+1)‐angulated core such that either G is not vertex‐transitive, or G is vertex‐transitive and any two maximum independent sets have non‐empty intersection. Then Gⁿ is a core for any positive integer n. On the other hand, let G_i be a (2κ_i+1)‐angulated core for 1 ≤ i≤ n where κ₁ < κ₂ < … < κ_n. If G_i has a vertex that is fixed under any automorphism for 1 ≤ i ≤ n‐1, or G_i is vertex‐transitive such that any two maximum independent sets have non‐empty intersection for 1 ≤ i ≤ n‐1, then □_i=1ⁿ G_i is a core. We then apply the results to construct cores that are box products with Mycielski construction factors or with odd graph factors. We also show that K(r,2r+1) □ C_2l+1 is a core for any integers l ≥ r ≥ 2. It is open whether K(r,2r+1) □ C_2l+1 is a core for r > l ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

On graphs with prescribed median I

The distance of a vertex u in a connected graph H is the sum of all the distances from u to the other vertices of H. The median M(H) of H is the subgraph of H induced by the vertices of minimum distance. For any graph G, let f(G) denote the minimum order of a connected graph H satisfying M(H) ? G. It is shown that if G has n vertices and minimum degree δ then f(G) ? 2n ? δ + 1. Graphs having both median and center prescribed are constructed. It is also shown that if the vertices of a K_r are removed from a graph H, then at most r components of the resulting graph contain median vertices of H.     

Sufficient conditions for λ′‐optimality in graphs with girth g

For a connected graph the restricted edge‐connectivity λ′(G) is defined as the minimum cardinality of an edge‐cut over all edge‐cuts S such that there are no isolated vertices in G–S. A graph G is said to be λ′‐optimal if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G defined as ξ(G) = min{d(u) + d(v) ? 2:uv ∈ E(G)}, d(u) denoting the degree of a vertex u. A. Hellwig and L. Volkmann [Sufficient conditions for λ′‐optimality in graphs of diameter 2, Discrete Math 283 (2004), 113–120] gave a sufficient condition for λ′‐optimality in graphs of diameter 2. In this paper, we generalize this condition in graphs of diameter g ? 1, g being the girth of the graph, and show that a graph G with diameter at most g ? 2 is λ′‐optimal. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 73–86, 2006     

On defect-d matchings in graphs

A defect-d matching in a graph G is a matching which covers all but d vertices of G. G is d-covered if each edge of G belongs to a defect-d matching. Here we characterise d-covered graphs and d-covered connected bipartite graphs. We show that a regular graph G of degree r which is (r ? 1)-edge-connected is 0-covered or 1-covered depending on whether G has an even or odd number of vertices, but, given any non-negative integers r and d, there exists a graph regular of degree r with connectivity and edge-connectivity r ? 2 which does not even have a defect-d matching. Finally, we prove that a vertex-transitive graph is 0-covered or 1-covered depending on whether it has an even or odd number of vertices.     

Total Domination in Graphs with Given Girth

A set S of vertices in a graph G without isolated vertices is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ _t (G) of G. In this paper, we establish an upper bound on the total domination number of a graph with minimum degree at least two in terms of its order and girth. We prove that if G is a graph of order n with minimum degree at least two and girth g, then γ _t (G) ≤ n/2 + n/g, and this bound is sharp. Our proof is an interplay between graph theory and transversals in hypergraphs. Michael A. Henning: Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

On induced Folkman numbers

In 1970, Folkman proved that for any graph G there exists a graph H with the same clique number as G. In addition, any r ‐coloring of the vertices of H yields a monochromatic copy of G. For a given graph G and a number of colors r let f(G, r) be the order of the smallest graph H with the above properties. In this paper, we give a relatively small upper bound on f(G, r) as a function of the order of G and its clique number. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 40, 493–500, 2012     

Sparse <Emphasis Type="Italic">H</Emphasis>-Colourable Graphs of Bounded Maximum Degree

Let F be a graph of order at most k. We prove that for any integer g there is a graph G of girth at least g and of maximum degree at most 5k¹³ such that G admits a surjective homomorphism c to F, and moreover, for any F-pointed graph H with at most k vertices, and for any homomorphism h from G to H there is a unique homomorphism f from F to H such that h=fc. As a consequence, we prove that if H is a projective graph of order k, then for any finite family of prescribed mappings from a set X to V(H) (with ||=t), there is a graph G of arbitrary large girth and of maximum degree at most 5k^26mt (where m=|X|) such that and up to an automorphism of H, there are exactly t homomorphisms from G to H, each of which is an extension of an f.Supported in part by the National Science Council under grant NSC89-2115-M-110-012Final version received: June 9, 2003     

Superconnectivity of regular graphs with small diameter

A graph is superconnected, for short super-κ, if all minimum vertex-cuts consist of the vertices adjacent with one vertex. In this paper we prove for any r-regular graph of diameter D and odd girth g that if D≤g−2, then the graph is super-κ when g≥5 and a complete graph otherwise.     

(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     

Representing groups by graphs with constant link and hypergraphs

A graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link L. We prove that for any finite group Γ and any disconnected link graph L with at least three vertices there are infinitely many connected graphs G with constant link L and AutG ? Γ. We look at the analogous problem for connected link graphs, namely, link graphs that are paths or have disconnected complements. Furthermore we prove that for n, r ≥ 2, but not n = 2 = r, any finite group can be represented by infinitely many connected r-uniform, n-regular hypergraphs of arbitrarily large girth.     

Minors in graphs of large girth

We show that for every odd integer g ≥ 5 there exists a constant c such that every graph of minimum degree r and girth at least g contains a minor of minimum degree at least cr^(g+1)/4. This is best possible up to the value of the constant c for g = 5, 7, and 11. More generally, a well‐known conjecture about the minimal order of graphs of given minimum degree and large girth would imply that our result gives the correct order of magnitude for all odd values of g. The case g = 5 of our result implies Hadwiger's conjecture for C₄‐free graphs of sufficiently large chromatic number. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 213–225, 2003     

Circumference and girth

Let G be 2-connected graph with girth g and minimum degree d. Then each pair of vertices of G is joined by a path of length at least max{1/2(d ? 1)g, (d ? 3/2)(g ? 4) + 2} if g ? 4, and the length of a longest cycle of G is at least max{[(d ? 1)(g ? 2) + 2], [(2d ? 3)(g ? 4) + 4]}.     

On bi-regular cages of even girth at least 8

Let r, m, 2 ≤ r < m and g ≥ 3 be three positive integers. A graph with a prescribed degree set r, m and girth g having the least possible number of vertices is called a bi-regular cage or an (r, m; g)-cage, and its order is denoted by n(r, m; g). In this paper we provide upper bounds on n(r, m; g) for some related values of r, m and even girth g at least 8. Moreover, if r ? 1 is a prime power and m ≥ 5, we construct the smallest currently known (r, m; 8)-graphs. Also, if r = 3 and m ≥ 7 is not divisible by 3, we prove that ${n(3,m; 8) \ge \lceil 25m/3\rceil + 7}$ . Finally, we construct a family of (3, m; 8)-graphs of order 9m + 3 which are cages for m = 4,5,7.     

On the connectivity and superconnected graphs with small diameter

In this paper, first we prove that any graph G is 2-connected if diam(G)≤g−1 for even girth g, and for odd girth g and maximum degree Δ≤2δ−1 where δ is the minimum degree. Moreover, we prove that any graph G of diameter diam(G)≤g−2 satisfies that (i) G is 5-connected for even girth g and Δ≤2δ−5, and (ii) G is super-κ for odd girth g and Δ≤3δ/2−1.     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

Dedicated to the memory of Paul Erdős A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph. Received May 13, 1999/Revised June 19, 2000     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008