Edge degrees and dominating cycles

The edge degree d(e) of the edge e=uv is defined as the number of neighbours of e, i.e., |N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G, if d(e₁)+d(e₂)>|V(G)|-4 for any remote edges e₁,e₂, then all longest cycles C in G are dominating, i.e., G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G is a 2-connected triangle-free graph with σ₂(G)>|V(G)|/2, then all longest cycles are dominating.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

Conditions on subgraphs,degrees, and domination for hamiltonian properties of graphs

Motivated by a hamiltonicity result due to Ageev, involving claw-free graphs with a small domination number, we study analogous conditions that guarantee different types of hamiltonian properties. In our first main result we relax the condition on claw-freeness and obtain a common generalization of the result of Ageev and a recent result due to Cai. Our other results deal with similar conditions that guarantee traceability, pancyclicity and hamiltonian-connectivity. We also leave some open problems.     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

A tight bound on the number of mobile servers to guarantee transferability among dominating configurations

In this paper, we propose a new framework to provide continuous services to users by a collection of mobile servers distributed over an interconnection network. We model those mobile servers as a subset of nodes, and assume that a user can receive the service if at least one adjacent node (including itself) plays the role of a server; i.e., we assume that the service could not be routed via the interconnection network. The main results obtained in this paper are summarized as follows: For the class of trees consisting of n nodes, ⌊n/2⌋ mobile servers are sometimes necessary and always sufficient to realize continuous services by the mobile servers, and for the class of Hamiltonian graphs with n nodes, ⌈(n+1)/3⌉ mobile servers are sometimes necessary and always sufficient.     

Degree sum and connectivity conditions for dominating cycles

For a graph G, let σ_k(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ₂(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ₃(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ₃(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ₄(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.     

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.     

Traceability of line graphs

Brualdi and Shanny [R.A. Brualdi, R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307-314], Clark [L. Clark, On hamitonian line graphs, J. Graph Theory 8 (1984) 303-307] and Veldman [H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229-239] gave minimum degree conditions of a line graph guaranteeing the line graph to be hamiltonian. In this paper, we investigate the similar conditions guaranteeing a line graph to be traceable. In particular, we show the following result: let G be a simple graph of order n and L(G) its line graph. If n is sufficiently large and, either ; or and G is almost bridgeless, then L(G) is traceable. As a byproduct, we also show that every 2-edge-connected triangle-free simple graph with order at most 9 has a spanning trail. These results are all best possible.     

A [k,k+1]-factor containing given Hamiltonian cycle

Letk⩾2 be an integer and let G be a graph of ordern with minimum degree at leastk, n⩾8k -16 for evenn and n⩾6k - 13 for oddn. If the degree sum of each pair of nonadjacent vertices of G is at least n, then for any given Hamiltonian cycleC. G has a [k, k + 1]-factor containingC Preject supported partially by an exchange program between the Chinese Academy of Sciences and the Japan Society for Promotion of Sciences and by the National Natural Science Foundation of China (Grant No. 19136012)     

Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is Ω(n^0.694), and the circumference of a 3-connected claw-free graph is Ω(n^0.121). We generalize and improve the first result by showing that every 3-edge-connected graph with m edges has an Eulerian subgraph with Ω(m^0.753) edges. We use this result together with the Ryjá?ek closure operation to improve the lower bound on the circumference of a 3-connected claw-free graph to Ω(n^0.753). Our proofs imply polynomial time algorithms for finding large Eulerian subgraphs of 3-edge-connected graphs and long cycles in 3-connected claw-free graphs.     

Cyclic hamiltonian cycle systems of the complete graph minus a 1-factor

In this paper, we prove that cyclic hamiltonian cycle systems of the complete graph minus a 1-factor, K_n-I, exist if and only if and n≠2p^α with p an odd prime and α?1.     

How to avoid using the Regularity Lemma: Pósa’s conjecture revisited

In this paper we investigate how the use of the Regularity Lemma and the Blow-up Lemma can be avoided in certain extremal problems of dense graphs. We present the ideas for the following well-known Pósa conjecture on the square of a Hamiltonian cycle. In 1962 Pósa conjectured that any graph G of order n and minimum degree at least contains the square of a Hamiltonian cycle. In an earlier paper we proved this conjecture with the use of the Regularity Lemma-Blow-up Lemma method for n≥n₀ where n₀ is very large. Here we present another proof (and a general method) that avoids the use of the Regularity Lemma and thus the resulting n₀ is much smaller.     

On Seymour’s strengthening of Hadwiger’s conjecture for graphs with certain forbidden subgraphs

Let H be a set of graphs. A graph is called H-free if it does not contain a copy of a member of H as an induced subgraph. If H is a graph then G is called H-free if it is {H}-free. Plummer, Stiebitz, and Toft proved that, for every -free graph H on at most four vertices, every -free graph G has a collection of ⌈|V(G)|/2⌉ many pairwise adjacent vertices and edges (where a vertexvand an edgeeare adjacent if v is disjoint from the set V(e) of endvertices of e and adjacent to some vertex of V(e), and two edgeseandfare adjacent if V(e) and V(f) are disjoint and some vertex of V(e) is adjacent to some vertex of V(f)). Here we generalize this statement to -free graphs H on at most five vertices.     

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     

Collapsible graphs and reductions of line graphs

A graph G is collapsible if for every even subset X⊆V(G), G has a subgraph Γ such that G−E(Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].     

Local search algorithms for finding the Hamiltonian completion number of line graphs

Given a graph G=(V,E), the Hamiltonian completion number of G, HCN(G), is the minimum number of edges to be added to G to make it Hamiltonian. This problem is known to be -hard even when G is a line graph. In this paper, local search algorithms for finding HCN(G) when G is a line graph are proposed. The adopted approach is mainly based on finding a set of edge-disjoint trails that dominates all the edges of the root graph of G. Extensive computational experiments conducted on a wide set of instances allow to point out the behavior of the proposed algorithms with respect to both the quality of the solutions and the computation time.     

Cyclic k‐cycle systems of order 2kn + k: A solution of the last open cases

We exhibit cyclic (K_v, C_k)‐designs with v > k, v ≡ k (mod 2k), for k an odd prime power but not a prime, and for k = 15. Such values were the only ones not to be analyzed yet, under the hypothesis v ≡ k (mod 2k). Our construction avails of Rosa sequences and approximates the Hamiltonian case (v = k), which is known to admit no cyclic design with the same values of k. As a particular consequence, we settle the existence question for cyclic (K_v, C_k)‐designs with k a prime power. © 2004 Wiley Periodicals, Inc. J Combin Designs 12: 299–310, 2004.