Critical graphs for subpancyclicity of 3‐connected claw‐free graphs

Let be the family of graphs G such that all sufficiently large k ‐connected claw‐free graphs which contain no induced copies of G are subpancyclic. We show that for every k≥3 the family is infinite and make the first step toward the complete characterization of the family . © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 263–278, 2009     

On factors of 4‐connected claw‐free graphs*

We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian, i.e., has a connected 2‐factor. Conjecture 2 (Matthews and Sumner): Every 4‐connected claw‐free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass‐free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125–136, 2001     

Every 3‐connected claw‐free Z8‐free graph is Hamiltonian

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P₃ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010     

Hourglasses and Hamilton cycles in 4‐connected claw‐free graphs

We show that if G is a 4‐connected claw‐free graph in which every induced hourglass subgraph S contains two non‐adjacent vertices with a common neighbor outside S, then G is hamiltonian. This extends the fact that 4‐connected claw‐free, hourglass‐free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 267–276, 2005     

Closure and stable Hamiltonian properties in claw‐free graphs

In the class of k‐connected claw‐free graphs, we study the stability of some Hamiltonian properties under a closure operation introduced by the third author. We prove that (i) the properties of pancyclicity, vertex pancyclicity and cycle extendability are not stable for any k (i.e., for any of these properties there is an infinite family of graphs G_k of arbitrarily high connectivity k such that the closure of G_k has the property while the graph G_k does not); (ii) traceability is a stable property even for k = 1; (iii) homogeneous traceability is not stable for k = 2 (although it is stable for k = 7). The article is concluded with several open questions concerning stability of homogeneous traceability and Hamiltonian connectedness. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 30–41, 2000     

Maximal K3's and Hamiltonicity of 4‐connected claw‐free graphs

Let cl(G) denote Ryjá?ek's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[N_G(T)] is cyclically 3‐connected if T is a maximal K₃ in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Hamilton connectivity of line graphs and claw‐free graphs

Let G be a graph and let V₀ = {ν∈ V(G): d_G(ν) = 6}. We show in this paper that: (i) if G is a 6‐connected line graph and if |V₀| ≤ 29 or G[V₀] contains at most 5 vertex disjoint K₄'s, then G is Hamilton‐connected; (ii) every 8‐connected claw‐free graph is Hamilton‐connected. Several related results known before are generalized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Upper total domination in claw‐free graphs

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S (other than itself). The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ_t(G). We establish bounds on Γ_t(G) for claw‐free graphs G in terms of the number n of vertices and the minimum degree δ of G. We show that if if , and if δ ≥ 5. The extremal graphs are characterized. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 148–158, 2003     

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

On stability of Hamilton‐connectedness under the 2‐closure in claw‐free graphs

It is easy to characterize chordal graphs by every k‐cycle having at least f(k) = k ? 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f(k) = 2?(k ? 3)/2?, and of the graphs whose blocks are trivially perfect using f(k) = 2k ? 7. These three functions f(k) are optimum in that each class contains graphs in which every k‐cycle has exactly f(k) chords. The functions 3?(k ? 3)/3? and 3k ? 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k‐cycles are replaced with k‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011     

Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs

In this paper, we show that if G is a 3‐edge‐connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

Claw‐free 3‐connected P11‐free graphs are hamiltonian

We show that every 3‐connected claw‐free graph which contains no induced copy of P₁₁ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of P₁₂ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 111–121, 2004     

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.     

Line graphs of multigraphs and Hamilton‐connectedness of claw‐free graphs

We introduce a closure concept that turns a claw‐free graph into the line graph of a multigraph while preserving its (non‐)Hamilton‐connectedness. As an application, we show that every 7‐connected claw‐free graph is Hamilton‐connected, and we show that the well‐known conjecture by Matthews and Sumner (every 4‐connected claw‐free graph is hamiltonian) is equivalent with the statement that every 4‐connected claw‐free graph is Hamilton‐connected. Finally, we show a natural way to avoid the non‐uniqueness of a preimage of a line graph of a multigraph, and we prove that the closure operation is, in a sense, best possible. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:152‐173, 2011     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003     

On the hamiltonicity of line graphs of locally finite, 6‐edge‐connected graphs

The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a weaker version of this result for infinite graphs: The line graph of locally finite, 6‐edge‐connected graph with a finite number of ends, each of which is thin, is hamiltonian.     

Hamiltonian properties of locally connected graphs with bounded vertex degree

We consider the existence of Hamiltonian cycles for the locally connected graphs with a bounded vertex degree. For a graph G, let Δ(G) and δ(G) denote the maximum and minimum vertex degrees, respectively. We explicitly describe all connected, locally connected graphs with Δ(G)?4. We show that every connected, locally connected graph with Δ(G)=5 and δ(G)?3 is fully cycle extendable which extends the results of Kikust [P.B. Kikust, The existence of the Hamiltonian circuit in a regular graph of degree 5, Latvian Math. Annual 16 (1975) 33-38] and Hendry [G.R.T. Hendry, A strengthening of Kikust’s theorem, J. Graph Theory 13 (1989) 257-260] on full cycle extendability of the connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for the locally connected graphs with Δ(G)?7 is NP-complete.     

Hamiltonian circuits in N2-locally connected K1,3-free graphs

There are many results concerned with the hamiltonicity of K_1,3-free graphs. In the paper we show that one of the sufficient conditions for the K_1,3-free graph to be Hamiltonian can be improved using the concept of second-type vertex neighborhood. The paper is concluded with a conjecture.     

An approximate version of Hadwiger's conjecture for claw‐free graphs

Hadwiger's conjecture states that every graph with chromatic number χ has a clique minor of size χ. In this paper we prove a weakened version of this conjecture for the class of claw‐free graphs (graphs that do not have a vertex with three pairwise nonadjacent neighbors). Our main result is that a claw‐free graph with chromatic number χ has a clique minor of size $\lceil\frac{2}{3}\chi\rceil$. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 259–278, 2010