共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
《Operations Research Letters》2006,34(3):269-274
We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs with worst case time complexity , where c is some fixed constant that does not depend on the instance. Furthermore, we show that under the exponential time hypothesis, the time complexity cannot be improved to . 相似文献
4.
Louis DeBiasio Robert A. Krueger Dan Pritikin Eli Thompson 《Journal of Graph Theory》2020,94(1):92-112
Chen et al determined the minimum degree threshold for which a balanced -partite graph has a Hamiltonian cycle. We give an asymptotically tight minimum degree condition for Hamiltonian cycles in arbitrary -partite graphs in that all parts have at most vertices (a necessary condition). To do this, we first prove a general result that both simplifies the process of checking whether a graph is a robust expander and gives useful structural information in the case when is not a robust expander. Then we use this result to prove that any -partite graph satisfying the minimum degree condition is either a robust expander or else contains a Hamiltonian cycle directly. 相似文献
5.
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 相似文献
6.
Ralph J. Faudree Ronald J. Gould Michael S. Jacobson Colton Magnant 《Journal of Graph Theory》2012,69(1):28-45
Let G be a graph of order n and 3≤t≤n/4 be an integer. Recently, Kaneko and Yoshimoto [J Combin Theory Ser B 81(1) (2001), 100–109] provided a sharp δ(G) condition such that for any set X of t vertices, G contains a hamiltonian cycle H so that the distance along H between any two vertices of X is at least n/2t. In this article, minimum degree and connectivity conditions are determined such that for any graph G of sufficiently large order n and for any set of t vertices X?V(G), there is a hamiltonian cycle H so that the distance along H between any two consecutive vertices of X is approximately n/t. Furthermore, the minimum degree threshold is determined for the existence of a hamiltonian cycle H such that the vertices of X appear in a prescribed order at approximately predetermined distances along H. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 28–45, 2012 相似文献
7.
ON THE CONSTRUCTION AND ENUMERATION OF HAMILTONIAN GRAPHS 总被引:1,自引:0,他引:1
In this paer we give a farmula for enumerating the equivalent classes of orderly labeled Hamiltonian graphs under group D.and two algorithms for constructing these equivalent classes and all nonisomorphic Hamiltonian graphs.Some computational results obtained by microcomputers are listed. 相似文献
8.
9.
A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with
, then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with
, then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2. 相似文献
10.
Gábor N. Sárközy 《Discrete Mathematics》2009,309(6):1611-1622
Suppose that 0<η<1 is given. We call a graph, G, on n vertices an η-Chvátal graph if its degree sequence d1≤d2≤?≤dn satisfies: for k<n/2, dk≤min{k+ηn,n/2} implies dn−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). 相似文献
11.
Jinfeng Feng 《Mathematical Methods of Operations Research》2009,69(2):343-352
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:
Under this assumption, we prove that G has a 2-dominating induced cycle and G is Hamiltonian.
J. Feng is an associate member of “Graduiertenkolleg: Hierarchie und Symmetrie in mathematischen Modellen (DFG)” at RWTH Aachen,
Germany. 相似文献
12.
We show how to find in Hamiltonian graphs a cycle of length nΩ(1/loglogn)=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n3) time a cycle in G of length kΩ(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n3) time a cycle of length kΩ(1/(log(n/k)+loglogn)), which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)kΩ(1), running in time O(n2) for planar graphs. 相似文献
13.
Hamiltonian cycles in Dirac graphs 总被引:1,自引:1,他引:0
We prove that for any n-vertex Dirac graph (graph with minimum degree at least n/2) G=(V,E), the number, Ψ(G), of Hamiltonian cycles in G is at least where h(G)=maxΣ e x e log(1/x e ), the maximum over x: E → ?+ satisfying Σ e?υ x e = 1 for each υ ∈ V, and log =log2. (A second paper will show that this bound is tight up to the o(n).)
We also show that for any (Dirac) G of minimum degree at least d, h(G) ≥ (n/2) logd, so that Ψ(G) > (d/(e + o(1))) n . In particular, this says that for any Dirac G we have Ψ(G) > n!/(2 + o(1)) n , confirming a conjecture of G. Sárközy, Selkow, and Szemerédi which was the original motivation for this work. 相似文献
$exp_2 [2h(G) - n\log e - o(n)],$
14.
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. 相似文献
15.
《Discrete Mathematics》2022,345(12):113069
The toughness of a noncomplete graph G is the maximum real number t such that the ratio of to the number of components of is at least t for every cutset S of G. Determining the toughness for a given graph is NP-hard. Chvátal's toughness conjecture, stating that there exists a constant such that every graph with toughness at least is hamiltonian, is still open for general graphs. A graph is called -free if it does not contain any induced subgraph isomorphic to , the disjoint union of and two isolated vertices. In this paper, we confirm Chvátal's toughness conjecture for -free graphs by showing that every 7-tough -free graph on at least three vertices is hamiltonian. 相似文献
16.
17.
Gerhard J. Woeginger 《Discrete Mathematics》1998,190(1-3):295-297
In this short note we argue that the toughness of split graphs can be computed in polynomial time. This solves an open problem from a recent paper by Kratsch et al. (Discrete Math. 150 (1996) 231–245). 相似文献
18.
A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v1, v2, …, vk of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v1, v2, …, vk in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999 相似文献
19.
Given a graph , let be the set of all cycle lengths contained in and let . Let and let be the greatest common divisor of and all the positive pairwise differences of elements in . We prove that if a Hamiltonian graph of order has at least edges, where is an integer such that , then or is exceptional, by which we mean for some . We also discuss cases where is not exceptional, for example when is prime. Moreover, we show that , which if is bipartite implies that , where is the number of edges in . 相似文献
20.
Triangulated irregular networks (TINs) are common representations of surfaces in computational graphics. We define the dual of a TIN in a special way, based on vertex-adjacency, and show that its Hamiltonian cycle always exists and can be found efficiently. This result has applications in transmission of large graphics datasets. 相似文献