Hamiltonian paths with prescribed edges in hypercubes

Given a set P of at most 2n-4 prescribed edges (n?5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube Q_n contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek who showed that for any n?3 there exist vertices u,v and 2n-3 edges of Q_n not contained in any hamiltonian path between u and v, but still satisfying the condition above. The proof of the main theorem is based on an inductive construction whose basis for n=5 was verified by a computer search. Classical results on hamiltonian edge-fault tolerance of hypercubes are obtained as a corollary.     

Matchings extend to Hamiltonian cycles in hypercubes with faulty edges

We consider the problem of existence of a Hamiltonian cycle containing a matching and avoiding some edges in an n-cube {{\displaystyle Q}}_n, and obtain the following results. Let n\ge \mathrm{3},\hspace{0.17em}M\subset E({{\displaystyle Q}}_n), and F\subset E({{\displaystyle Q}}_n)\backslash M with \mathrm{1}\le \left|F\right|\le \mathrm{2}n-\mathrm{4}-\left|M\right|. If M is a matching and every vertex is incident with at least two edges in the graph {{\displaystyle Q}}_n-F, then all edges of M lie on a Hamiltonian cycle in {{\displaystyle Q}}_n-F. Moreover, if \left|M\right|=\mathrm{1} or \left|M\right|=\mathrm{2}, then the upper bound of number of faulty edges tolerated is sharp. Our results generalize the well-known result for \left|M\right|=\mathrm{1}.     

Independent dominating sets and hamiltonian cycles

A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no r‐regular uniquely hamiltonian graphs when r > 22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233–244, 2007     

正圆有向图中的弧不相交的Hamilton路和圈

2012年,Bang-Jensen和Huang(J.Combin.Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想.主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈,并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路,使得它们两两弧不相交.由于任意圆有向图一定是正圆有向图,所得结论可以推广到圆有向图中.又由于圆有向图是局部竞赛图的子图类,因此所得结论说明对局部竞赛图的子图类――圆有向图,Bang-Jensen和Huang的猜想成立.     

Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs

In 1956, W.T. Tutte proved that every 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. It is shown that Sanders’ result is best possible by constructing 4-connected maximal planar graphs with three edges a large distance apart such that any hamiltonian cycle misses one of them. If the maximal planar graph is 5-connected then such a construction is impossible.     

Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges

The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e., pairwise vertex-disjoint paths） in the 3-ary n-cube Qn^3 with faulty edges. The following result is obtained. Let E0 （≠θ） be a linear forest and F （≠θ） be a set of faulty edges in Q3 such that E0∩ F = 0 and ｜E0｜ ＋｜F｜ ≤ 2n - 2. Then all edges of E0 lie on a Hamiltonian cycle in Qn^3- F, and the upper bound 2n - 2 is sharp.     

Hamiltonian cycles in n‐extendable graphs

A graph G of order at least 2n+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy deg_G x+deg_G y ≥ p ? n ? 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002     

Hamiltonian cycles and 2-dominating induced cycles in claw-free graphs

Let G = (V, E) be a connected graph. For a vertex subset , G[S] is the subgraph of G induced by S. A cycle C (a path, respectively) is said to be an induced cycle (path, respectively) if G[V(C)] = C (G[V(P)] = P, respectively). The distance between a vertex x and a subgraph H of G is denoted by , where d(x, y) is the distance between x and y. A subgraph H of G is called 2-dominating if d(x, H) ≤ 2 for all . An induced path P of G is said to be maximal if there is no induced path P′ satisfying and . In this paper, we assume that G is a connected claw-free graph satisfying the following condition: for every maximal induced path P of length p ≥ 2 with end vertices u, v it holds:

Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes

Recently, Fink [J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory Ser. B 97 (2007) 1074-1076] affirmatively answered Kreweras’ conjecture asserting that every perfect matching of the hypercube extends to a Hamiltonian cycle. We strengthen this result in the following way. Given a partition of the hypercube into subcubes of nonzero dimensions, we show for every perfect matching of the hypercube that it extends on these subcubes to a Hamiltonian cycle if and only if it interconnects them.     

Long alternating paths in bicolored point sets

Given n red and n blue points in convex position in the plane, we show that there exists a noncrossing alternating path of length . We disprove a conjecture of Erd?s by constructing an example without any such path of length greater than .     

Independent sets and non-augmentable paths in generalizations of tournaments

We study different classes of digraphs, which are generalizations of tournaments, to have the property of possessing a maximal independent set intersecting every non-augmentable path (in particular, every longest path). The classes are the arc-local tournament, quasi-transitive, locally in-semicomplete (out-semicomplete), and semicomplete k-partite digraphs. We present results on strongly internally and finally non-augmentable paths as well as a result that relates the degree of vertices and the length of longest paths. A short survey is included in the introduction.     

Long paths and cycles in random subgraphs of graphs with large minimum degree

For a given finite graph G of minimum degree at least k, let G_p be a random subgraph of G obtained by taking each edge independently with probability p. We prove that (i) if for a function that tends to infinity as k does, then G_p asymptotically almost surely contains a cycle (and thus a path) of length at least , and (ii) if , then G_p asymptotically almost surely contains a path of length at least k. Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking G to be the complete graph on k + 1 vertices. © Wiley Periodicals, Inc. Random Struct. Alg., 46, 320–345, 2015     

Long cycles in graphs without hamiltonian paths

For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. Bondy and Locke [J.A. Bondy, S.C. Locke, Relative length of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122] consider the gap between p(G) and c(G) in 3-connected graphs G. Starting with this result, there are many results appeared in this context, see [H. Enomoto, J. van den Heuvel, A. Kaneko, A. Saito, Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory 20 (1995) 213-225; M. Lu, H. Liu, F. Tian, Relative length of longest paths and cycles in graphs, Graphs Combin. 23 (2007) 433-443; K. Ozeki, M. Tsugaki, T. Yamashita, On relative length of longest paths and cycles, preprint; I. Schiermeyer, M. Tewes, Longest paths and longest cycles in graphs with large degree sums, Graphs Combin. 18 (2002) 633-643]. In this paper, we investigate graphs G with p(G)−c(G) at most 1 or at most 2, but with no hamiltonian paths. Let G be a 2-connected graph of order n, which has no hamiltonian paths. We show two results as follows: (i) if , then p(G)−c(G)≤1, and (ii) if σ₄(G)≥n+3, then p(G)−c(G)≤2.     

On the number of increasing paths in labeled cycles and stars

A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2 uk） （k ≥ 2） in G such that L（u,） ＋ 2 ≤ L（ui＋1） for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in （G, L） is denoted by d（G, L）. A labeling L is optimal if the labeling L produces the largest d（G, L）. In this paper, a method simpler than that in Zverovich （2004） to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.     

赋权图中的路和圈

本文研究了赋权图中的最长路和最长圈,将关于非赋权图中最长路和最长圈的一些结果推广到赋权图上.     

Cycles and paths in edge‐colored graphs with given degrees

Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ?(n+1)/2? has properly edge‐colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge‐colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010     

A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

Suppose that 0<η<1 is given. We call a graph, G, on n vertices an η-Chvátal graph if its degree sequence d₁≤d₂≤?≤d_n satisfies: for k<n/2, d_k≤min{k+ηn,n/2} implies d_n−k−ηn≥n−k. (Thus for η=0 we get the well-known Chvátal graphs.) An -algorithm is presented which accepts as input an η-Chvátal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best -algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs (δ(G)≥n/2 where δ(G) is the minimum degree in G).