Rotation numers for complete bipartite graphs

A rooted graph is a pair (G, x) where G is a simple undirected graph and x ? V(G). If G if rooted at x, then its rotation number h(G, x) is teh minimum number of edges in a graph F, of the same order as G, such that for all v ? V(F) we can find a copy of G in F with the root x at v. Rotation numbers for complete bipartite graphs were itroduced in [4] by Cockayne and Lorimer. Several cases were evaluated by Bollobás and Cockayne in [2], and in this paper we give a full solution.     

Factoring cartesian-product graphs

In a fundamental paper, G. Sabidussi [“Graph Multiplication,” Mathematische Zeitschrift, Vol. 72 (1960), pp. 446–457] used a tower of equivalence relations on the edge set E(G) of a connected graph G to decompose G into a Cartesian product of prime graphs. Later, a method by R.L. Graham and P.M. Winkler [“On Isometric Embeddings of Graphs,” Transactions of the American Mathematics Society, Vol. 288 (1985), pp. 527–533] of embedding a connected graph isometrically into Cartesian products opened another approach to this problem. In both approaches an equivalence relation σ that determines the prime factorization is constructed. The methods differ by the starting relations used. We show that σ can be obtained as the convex hull of the starting relation used by Sabidussi. Our result also holds for the relation determining the prime decomposition of infinite connected graphs with respect to the weak Cartesian product. Moreover, we show that this relation is the transitive closure of the union of the starting relations of Sabidussi and Winkler [“Factoring a Graph in Polynomial Time,” European Journal of Combinatorics, Vol. 8 (1987), pp. 209–212], thereby generalizing the result of T. Feder [“Product Graph Representations,” Journal of Graph Theory, Vol 16 (1993), pp. 467–488] from finite to infinite graphs.     

The ratio of the distance irredundance and domination numbers of a graph

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n-dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n-dominating sets of G is called the n-domination number of G and is denoted by γ_n(G). A set / of vertices in G is n-irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / - {x}. The n-irredundance number of G, denoted by ir_n(G), is the minimum cardinality taken over all maximal n-irredundant sets of vertices of G. We show that inf{ir_n(G)/γ_n(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_n(T)/γ_n(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph-Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].     

The construction of tutte's 8-cage and the conder graph

A unified way is described of constructing two 5-are-transitive graphs of valency 3, the Tutte 8-cage, and the Conder graph. It well illustrates the method of constructing symmetric graphs described in P. Lorimer “Vertex Transitive Graphs: Symmetric Graphs of Prime Valency,” Journal of Graph Theory, 8 (1984, 55–68).     

A degree condition for a graph to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1 ≤ a < b. We show that G has an [a, b]-factor if δ(G) ≥ a, n ≥ 2a + b + and max {d_G(u), d_G(v) ≥ for any two nonadjacent vertices u and v in G. This result is best possible, and it is an extension of T. Iida and T. Nishimura's results (T. Iida and T. Nishimura, An Ore-type condition for the existence of k-factors in graphs, Graphs and Combinat. 7 (1991), 353–361; T. Nishimura, A degree condition for the existence of k-factors, J. Graph Theory 16 (1992), 141–151). about the existence of a k-factor. As an immediate consequence, it shows that a conjecture of M. Kano (M. Kano, Some current results and problems on factors of graphs, Proc. 3rd China–USA International Conference on Graph Theory and Its Application, Beijing (1993). about connected [a, b]-factors is incorrect. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 1–6, 1998     

Cycle lengths in graphs with large minimum degree

Our main result is the following theorem. Let k ≥ 2 be an integer, G be a graph of sufficiently large order n, and δ(G) ≥ n/k. Then:

• (i) G contains a cycle of length t for every even integer t ∈ [4, δ(G) + 1].
• (ii) If G is nonbipartite then G contains a cycle of length t for every odd integer t ∈ [2k ? 1, δ(G) + 1], unless k ≥ 6 and G belongs to a known exceptional class.

© 2006 Wiley Periodicals, Inc. J Graph Theory 52: 157–170, 2006     

Edge-maximal (k,i)-graphs

A graph G is a (k, l)-graph if for any subgraph H of G, that |V(H)| ≧ implies that k(H) ≦ k ? 1. An edge-maximal (k, l-graph G is one such that for any e ? E(G^c), G + e is not a (k, l)-graph. In [F. T. Boesch and J. A. M. McHugh, ?An Edge Extremal Result for Subcohesion,”? Journal of Combinatorial Theory B, vol. 38 (1985), pp. 1–7] a class of edge-maximal graphs was found and used to show best possible upper bounds of the size of edge-maximal (k, l)-graphs. In this paper, we investigate the lower bounds of the size of edge-maximal (k, l)-graphs. Let f(n, k, l) denote the minimum size of edge-maximal (k, l)-graphs of order n. We shall give a characterization of edge-maximal (k, l)-graphs. This characterization is used to determine f(n, k, l) and to characterize the edge-maximal (k, l)-graphs with minimum sizes, for all n ≦ k + 2 ≦ 5. Thus prior results in [F.T. Boesch and J. A. M. McHugh, op. cit.; H.-J. Lai, ?The Size of Strength-Maximal Graphs,”? Journal of Graph Theory, vol. 14 (1990), pp. 187–197] are extended.     

Rotation numbers for complete tripartite graphs

Arooted graph is a pair (G, x), whereG is a simple undirected graph andx V(G). IfG is rooted atx, then itsrotation number h(G, x) is the minimum number of edges in a graphF of the same order asG such that for allv V(F), we can find a copy ofG inF with the rootx atv. Rotation numbers for all complete bipartite graphs are now known (see [2], [4], [7]). In this paper we calculate rotation numbers for complete tripartite graphs with rootx in the largest vertex class.Funded by the Science and Engineering Research Council.     

Connectivity keeping paths in k‐connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.     

Search algorithm for Ramsey graphs by union of group orbits

An algorithm for the construction of Ramsey graphs with a given automorphism group G is presented. To find a graph on n vertices with no clique of k vertices, K_k, and no independent set of l vertices, ¯K_l, k, l ≤ n, with an automorphism group G, a Boolean formula α based on the G-orbits of k-subsets and l-subsets of vertices is constructed from incidence matrices belonging to G. This Boolean formula is satisfiable if and only if the desired graph exists, and each satisfying assignment to α specifies a set of orbits of pairs of vertices whose union gives the edges of such a graph. Finding these assignments is basically equivalent to the conversion of α from CNF to DNF (conjunctive to disjunctive normal form). Though the latter problem is NP-hard, we present an “efficient” method to do the conversion for the formulas that appear in this particular problem. When G is taken to be the dihedral group D_n for n ≤ 101, this method matches all of the previously known cyclic Ramsey graphs, as reported by F. R. K. Chung and C. M. Grinstead [“A Survey of Bounds for Classical Ramsey Numbers,” Journal of Graph Theory, 7 (1983), 25–38], in dramatically smaller computer time when compared to the time required by an exhaustive search. Five new lower bounds for the classical Ramsey numbers are established: R(4, 7) ? 47, R(4, 8) ? 52, R(4, 9) ? 69, R(5,7) ? 76, and R(5, 8) ? 94. Also, some previously known cyclic graphs are shown to be unique up to isomorphism.     

Chromaticity of triangulated graphs

It is shown here that a connected graph G without subgraphs isomorphic to K₄ is triangulated if and only if its chromatic polynomial P(G,λ) equals λ(λ ? 1)^m(λ ? 2)^r for some integers m ≧ 1, r ≧ 0. This result generalizes the characterization of Two-Trees given by E.G. Whitehead [“Chromaticity of Two-Trees,” Journal of Graph Theory 9 (1985) 279–284].     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

The ratio of the irredundance number and the domination number for block-cactus graphs

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43–56] and Bollobás and Cockayne [J. Graph Theory (1979) 241–249] proved independently that γ(G) < 2ir(G) for any graph G. For a tree T, Damaschke [Discrete Math. (1991) 101–104] obtained the sharper estimation 2γ(T) < 3ir(T). Extending Damaschke's result, Volkmann [Discrete Math. (1998) 221–228] proved that 2γ(G) ≤ 3ir(G) for any block graph G and for any graph G with cyclomatic number μ(G) ≤ 2. Volkmann also conjectured that 5γ(G) < 8ir(G) for any cactus graph. In this article we show that if G is a block-cactus graph having π(G) induced cycles of length 2 (mod 4), then γ(G)(5π(G) + 4) ≤ ir(G)(8π(G) + 6). This result implies the inequality 5γ(G) < 8ir(G) for a block-cactus graph G, thus proving the above conjecture. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 139–149, 1998     

Connectivity keeping trees in k‐connected graphs

We show that one can choose the minimum degree of a k‐connected graph G large enough (independent of the vertex number of G) such that G contains a copy T of a prescribed tree with the property that G ? V(T) remains k‐connected. This was conjectured in [W. Mader, J Graph Theory 65 (2010), 61–69]. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 324–329, 2012     

On the acyclic choosability of graphs

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is L‐list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper coloring c of G such that c (v) ∈ L(v) for all v ∈ V. If G is L‐list colorable for every list assignment with |L (v)| ≥ k for all v ∈ V, then G is said k‐choosable. A graph is said to be acyclically k‐choosable if the obtained coloring is acyclic. In this paper, we study the links between acyclic k‐choosability of G and Mad(G) defined as the maximum average degree of the subgraphs of G and give some observations about the relationship between acyclic coloring, choosability, and acyclic choosability. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 281–300, 2006     

ON UNIQUELY -G k-COLOURABLE GRAPHS

Abstract

Given graphs F and G and a nonnegative integer k, a map Π: V(F) → + {lm …, k} is a -G k-colouring of F if the subgraphs induced by each colour class do not contain G as an induced subgraph; F is -G k-chromatic if F has a -G k-colouring but no -G (k—1)-colouring. Further, we say F is uniquely -G k-colourable if and only if F is -G k-chromatic and, up to a permutation of colours, it has only one -G k-colouring. Such notions are extensions of the well known corresponding definitions from chromatic theory. In a previous paper (J. Graph. Th. 11 (1987), 87–99), the authors conjectured that for all graphs G of order at least two and all nonnegative integers k there exist uniquely -G k-colourable graphs. We show here that the conjecture holds whenever G or its complement is 2-connected.     

Short proofs for two theorems of Chien,Hell and Zhu

In (J Graph Theory 33 (2000), 14–24), Hell and Zhu proved that if a series–parallel graph G has girth at least 2?(3k?1)/2?, then χ_c(G)≤4k/(2k?1). In (J Graph Theory 33 (2000), 185–198), Chien and Zhu proved that the girth condition given in (J Graph Theory 33 (2000), 14–24) is sharp. Short proofs of both results are given in this note. © 2010 Wiley Periodicals, Inc. J Graph 66: 83‐88, 2010 Theory     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

On stability of the hamiltonian index under contractions and closures

The hamiltonian index of a graph G is the smallest integer k such that the k‐th iterated line graph of G is hamiltonian. We first show that, with one exceptional case, adding an edge to a graph cannot increase its hamiltonian index. We use this result to prove that neither the contraction of an A_G(F)‐contractible subgraph F of a graph G nor the closure operation performed on G (if G is claw‐free) affects the value of the hamiltonian index of a graph G. AMS Subject Classification (2000): 05C45, 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Subgraph‐avoiding coloring of graphs

Given a “forbidden graph” F and an integer k, an F‐avoiding k‐coloring of a graph G is a k‐coloring of the vertices of G such that no maximal F‐free subgraph of G is monochromatic. The F‐avoiding chromatic number ac_F(G) is the smallest integer k such that G is F‐avoiding k‐colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that ac_F(G) ? C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for ac_F(G) in terms of various invariants of G are also given. Particularly, we prove that ${{ac}}_{{{F}}}({{G}})\le {{2}}\lceil\sqrt{{{n}}}\rceil+{{1}}Given a “forbidden graph” F and an integer k, an F‐avoiding k‐coloring of a graph G is a k‐coloring of the vertices of G such that no maximal F‐free subgraph of G is monochromatic. The F‐avoiding chromatic number ac_F(G) is the smallest integer k such that G is F‐avoiding k‐colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that ac_F(G) ? C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for ac_F(G) in terms of various invariants of G are also given. Particularly, we prove that ${{ac}}_{{{F}}}({{G}})\le {{2}}\lceil\sqrt{{{n}}}\rceil+{{1}}$, where n is the order of G and F is not K_k or $\overline{{{K}}_{{{k}}}}$. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 300–310, 2010