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     

A result on Hamiltonian line graphs involving restrictions on induced subgraphs

It is shown that the existence of a Hamilton cycle in the line graph of a graph G can be ensured by imposing certain restrictions on certain induced subgraphs of G. Thereby a number of known results on hamiltonian line graphs are improved, including the earliest results in terms of vertex degrees. One particular consequence is that every graph of diameter 2 and order at least 4 has a hamiltonian line graph.     

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 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.     

On s‐Hamiltonian Line Graphs

For an integer s ≥ 0, a graph G is s‐hamiltonian if for any vertex subset with |S^′| ≤ s, G ‐ S^′ is hamiltonian. It is well known that if a graph G is s‐hamiltonian, then G must be (s+2)‐connected. The converse is not true, as there exist arbitrarily highly connected nonhamiltonian graphs. But for line graphs, we prove that when s ≥ 5, a line graph is s‐hamiltonian if and only if it is (s+2)‐connected.     

Schrijver图SG(2k+2,k)的Hamilton性

通过图G的每个顶点的路称为Hamilton路,通过图G的每个顶点的圈称为Hamilton圈,具有Hamilton圈的图G称为Hamilton图.1952年Dirac曾得到关于Hamilton图一个充分条件的结论:图G有n个顶点,如果每个顶点υ满足:d(υ)≥n/2,则图G是Hamilton图.本文研究了Schrijver图SG(2k+2,k)的Hamilton性,采用寻找Hamilton圈的方法得出了Schrijver图SG(2k+2,k)是Hamilton图.     

Heavy cycles passing through some specified vertices in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex υ is called the weighted degree of υ. The weight of a cycle is defined as the sum of the weights of its edges. In this paper, we prove that: (1) if G is a 2‐connected weighted graph such that the minimum weighted degree of G is at least d, then for every given vertices x and y, either G contains a cycle of weight at least 2d passing through both of x and y or every heaviest cycle in G is a hamiltonian cycle, and (2) if G is a 2‐connected weighted graph such that the weighted degree sum of every pair of nonadjacent vertices is at least s, then for every vertex y, G contains either a cycle of weight at least s passing through y or a hamiltonian cycle. AMS classification: 05C45 05C38 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs. Received: September 13, 2001 Final version received: May 17, 2002 RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) RID="†" ID="†" Supported by RUTCOR RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) 05C75, 05C69 Acknowledgments. The authors thank the referees for valuable suggestions.     

Closure for the property of having a hamiltonian prism

We prove that a graph G of order n has a hamiltonian prism if and only if the graph Cl_4n/3–4/3(G) has a hamiltonian prism where Cl_4n/3–4/3(G) is the graph obtained from G by sequential adding edges between non‐adjacent vertices whose degree sum is at least 4n/3–4/3. We show that this cannot be improved to less than 4n/3–5. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 209–220, 2007     

A Closure for 1‐Hamilton‐Connectedness in Claw‐Free Graphs

A graph G is 1‐Hamilton‐connected if is Hamilton‐connected for every vertex . In the article, we introduce a closure concept for 1‐Hamilton‐connectedness in claw‐free graphs. If is a (new) closure of a claw‐free graph G, then is 1‐Hamilton‐connected if and only if G is 1‐Hamilton‐connected, is the line graph of a multigraph, and for some , is the line graph of a multigraph with at most two triangles or at most one double edge. As applications, we prove that Thomassen's Conjecture (every 4‐connected line graph is hamiltonian) is equivalent to the statement that every 4‐connected claw‐free graph is 1‐Hamilton‐connected, and we present results showing that every 5‐connected claw‐free graph with minimum degree at least 6 is 1‐Hamilton‐connected and that every 4‐connected claw‐free and hourglass‐free graph is 1‐Hamilton‐connected.     

The hamiltonian index of a 2-connected graph

Let G be a graph. Then the hamiltonian index h(G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l≥3. We also show that for any two 2-connected nonhamiltonian graphs G and with at least 74 vertices. The upper bounds are all sharp.     

Diameter vulnerability of GC graphs

Concern over fault tolerance in the design of interconnection networks has stimulated interest in finding large graphs with maximum degree Δ and diameter D such that the subgraphs obtained by deleting any set of s vertices have diameter at most D′, this value being close to D or even equal to it. This is the so-called (Δ,D,D′,s)-problem. The purpose of this work has been to study this problem for s=1 on some families of generalized compound graphs. These graphs were designed by Gómez (Ars Combin. 29-B (1990) 33) as a contribution to the (Δ,D)-problem, that is, to the construction of graphs having maximum degree Δ, diameter D and an order large enough. When approaching the mentioned problem in these graphs, we realized that each of them could be redefined as a compound graph, the main graph being the underlying graph of a certain iterated line digraph. In fact, this new characterization has been the key point to prove in a suitable way that the graphs belonging to these families are solutions to the (Δ,D,D+1,1)-problem.     

The Circular Flow Number of a 6-Edge Connected Graph is Less Than Four

We show that every 6-edge connected graph admits a circulation whose range lies in the interval [1,3). Received March 29, 2000 RID="*" ID="*" Supported by NATO-CNR Fellowship; this work was done while the author was visiting the Dept. of Mathematics and Statistics at Simon Fraser University, Canada. RID="†" ID="†" Supported by a National Sciences and Engineering Research Council Research Grant     

A generalization of Tutte’s theorem on Hamiltonian cycles in planar graphs

In 1956, W.T. Tutte proved that a 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. We prove that a planar graph G has a cycle containing a given subset X of its vertex set and any two prescribed edges of the subgraph of G induced by X if |X|≥3 and if X is 4-connected in G. If X=V(G) then Sanders’ result follows.     

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     

On graphs whose square have strong hamiltonian properties

The squareG² of a graph G is the graph having the same vertex set as G and two vertices are adjacent if and only if they are at distance at most 2 from each other. It is known that if G has no cut-vertex, then G² is Hamilton-connected (see [G. Chartrand, A.M. Hobbs, H.A. Jung, S.F. Kapoor, C.St.J.A. Nash-Williams, The square of a block is hamiltonian connected, J. Combin. Theory Ser. B 16 (1974) 290-292; R.J. Faudree and R.H. Schelp, The square of a block is strongly path connected, J. Combin. Theory Ser. B 20 (1976) 47-61]). We prove that if G has only one cut-vertex, then G² is Hamilton-connected. In the case that G has only two cut-vertices, we prove that if the block that contains the two cut-vertices is hamiltonian, then G² is Hamilton-connected. Further, we characterize all graphs with at most one cycle having Hamilton-connected square.     

The Hamiltonian Index of a Graph

 It is proved that the hamiltonian index of a connected graph other than a path is less than its diameter which improves the results of P. A. Catlin etc. [J. Graph Theory 14 (1990) 347–364] and M. L. Sarazin [Discrete Math. 134(1994)85–91]. Nordhaus-Gaddum's inequalities for the hamiltonian index of a graph are also established. Received: July 17, 1998 Final version received: September 13, 1999     

New constructions of hypohamiltonian and hypotraceable graphs

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14].