Perfect matchings extend to two or more hamiltonian cycles in hypercubes

Kreweras conjectured that every perfect matching of a hypercube $Q_n$ for $n\ge 2$ can be extended to a hamiltonian cycle of $Q_n$. Fink confirmed the conjecture to be true. It is more general to ask whether every perfect matching of $Q_n$ for $n\ge 2$ can be extended to two or more hamiltonian cycles of $Q_n$. In this paper, we prove that every perfect matching of $Q_n$ for $n\ge 4$ can be extended to at least $2^{2^{n?4}}$ different hamiltonian cycles of $Q_n$.     

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

Perfect matchings and Hamiltonian cycles in the preferential attachment model

In this paper, we study the existence of perfect matchings and Hamiltonian cycles in the preferential attachment model. In this model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection with m random vertices selected with probabilities proportional to their current degrees. (Constant m is the only parameter of the model.) We prove that if , then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamiltonian cycle asymptotically almost surely, provided that . One difficulty in the analysis comes from the fact that vertices establish connections only with vertices that are “older” (ie, are created earlier in the process). However, the main obstacle arises from the fact that edges in the preferential attachment model are not generated independently. In view of that, we also consider a simpler setting—sometimes called uniform attachment—in which vertices are added one by one and each vertex connects to m older vertices selected uniformly at random and independently of all other choices. We first investigate the existence of perfect matchings and Hamiltonian cycles in the uniform attachment model, and then extend the argument to the preferential attachment version.     

Hamiltonian cycles in k-partite graphs

Chen et al determined the minimum degree threshold for which a balanced $k$-partite graph has a Hamiltonian cycle. We give an asymptotically tight minimum degree condition for Hamiltonian cycles in arbitrary $k$-partite graphs in that all parts have at most $n/2$ vertices (a necessary condition). To do this, we first prove a general result that both simplifies the process of checking whether a graph $G$ is a robust expander and gives useful structural information in the case when $G$ is not a robust expander. Then we use this result to prove that any $k$-partite graph satisfying the minimum degree condition is either a robust expander or else contains a Hamiltonian cycle directly.     

Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

The minimum forcing number of perfect matchings in the hypercube

Let $M$ be a perfect matching in a graph. A subset $S$ of $M$ is said to be a forcing set of $M$, if $M$ is the only perfect matching in the graph that contains $S$. The minimum size of a forcing set of $M$ is called the forcing number of $M$. Pachter and Kim (1998) conjectured that the forcing number of every perfect matching in the $n$-dimensional hypercube is $2^{n?2}$, for all $n\ge 2$. This was revised by Riddle (2002), who conjectured that it is at least $2^{n?2}$, and proved it for all even $n$. We show that the revised conjecture holds for all $n\ge 2$. The proof is based on simple linear algebra.     

On the role of hypercubes in the resonance graphs of benzenoid graphs

The resonance graph R(B) of a benzenoid graph B has the perfect matchings of B as vertices, two perfect matchings being adjacent if their symmetric difference forms the edge set of a hexagon of B. A family P of pair-wise disjoint hexagons of a benzenoid graph B is resonant in B if B-P contains at least one perfect matching, or if B-P is empty. It is proven that there exists a surjective map f from the set of hypercubes of R(B) onto the resonant sets of B such that a k-dimensional hypercube is mapped into a resonant set of cardinality k.     

Perfect matchings in large uniform hypergraphs with large minimum collective degree

We define a perfect matching in a k-uniform hypergraph H on n vertices as a set of ⌊n/k⌋ disjoint edges. Let δk−1(H) be the largest integer d such that every (k−1)-element set of vertices of H belongs to at least d edges of H.In this paper we study the relation between δk−1(H) and the presence of a perfect matching in H for k?3. Let t(k,n) be the smallest integer t such that every k-uniform hypergraph on n vertices and with δk−1(H)?t contains a perfect matching.For large n divisible by k, we completely determine the values of t(k,n), which turn out to be very close to n/2−k. For example, if k is odd and n is large and even, then t(k,n)=n/2−k+2. In contrast, for n not divisible by k, we show that t(k,n)∼n/k.In the proofs we employ a newly developed “absorbing” technique, which has a potential to be applicable in a more general context of establishing existence of spanning subgraphs of graphs and hypergraphs.     

Gray codes extending quadratic matchings

Is it true that every matching in the n-dimensional hypercube can be extended to a Gray code? More than two decades have passed since Ruskey and Savage asked this question and the problem still remains open. A solution is known only in some special cases, including perfect matchings or matchings of linear size. This article shows that the answer to the Ruskey–Savage problem is affirmative for every matching of size at most . The proof is based on an inductive construction that extends balanced matchings in the completion of the hypercube by edges of into a Hamilton cycle of . On the other hand, we show that for every there is a balanced matching in of size that cannot be extended in this way.     

Hamiltonian cycles in -circulant digraphs

Let D be the circulant digraph with n vertices and connection set {2,3,c}. (Assume D is loopless and has outdegree 3.) Work of S. C. Locke and D. Witte implies that if n is a multiple of 6, c{(n/2)+2,(n/2)+3}, and c is even, then D does not have a hamiltonian cycle. For all other cases, we construct a hamiltonian cycle in D.     

Perfect matchings and the octahedron recurrence

We study a recurrence defined on a three dimensional lattice and prove that its values are Laurent polynomials in the initial conditions with all coefficients equal to one. This recurrence was studied by Propp and by Fomin and Zelivinsky. Fomin and Zelivinsky were able to prove Laurentness and conjectured that the coefficients were 1. Our proof establishes a bijection between the terms of the Laurent polynomial and the perfect matchings of certain graphs, generalizing the theory of Aztec Diamonds. In particular, this shows that the coefficients of this polynomial, and polynomials obtained by specializing its variables, are positive, a conjecture of Fomin and Zelevinsky.     

On certain Hamiltonian cycles in planar graphs

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least distinct Hamiltonian cycles. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 81–96, 1999     

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:

正圆有向图中的弧不相交的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 in bipartite quadrangulations on the torus

In this article, we shall prove that every bipartite quadrangulation G on the torus admits a simple closed curve visiting each face and each vertex of G exactly once but crossing no edge. As an application, we conclude that the radial graph of any bipartite quadrangulation on the torus has a hamiltonian cycle. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69:143‐151, 2012     

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.     

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.     

Lexicographic matchings cannot form Hamiltonian cycles

For any positive integer k let B(k) denote the bipartite graph of k- and k+1-element subsets of a 2k+1-element set with adjacency given by containment. It has been conjectured that for all k, B(k) is Hamiltonian. Any Hamiltonian cycle would be the union of two (perfect) matchings. Here it is shown that for all k>1 no Hamiltonian cycle in B(k) is the union of two lexicographic matchings.Supported by Office of Naval Research Contract N00014-85-K-0769.Supported by NSERC grants 69-3378 and 69-0259.     

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