共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
3.
For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant cD such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−cD if and only if for every n≥cD+3, has a cycle of order at least n−cD. Furthermore, we discuss some consequences and variants of this result. 相似文献
4.
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 相似文献
5.
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]. 相似文献
6.
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. 相似文献
7.
8.
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). 相似文献
9.
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. 相似文献
10.
11.
《Discrete Mathematics》2022,345(10):112989
A mixed graph is cospectral to its converse, with respect to the usual adjacency matrices. Hence, it is easy to see that a mixed graph whose eigenvalues occur uniquely, up to isomorphism, must be isomorphic to its converse. It is therefore natural to ask whether or not this is a common phenomenon. This note contains the theoretical evidence to confirm that the fraction of self-converse mixed graphs tends to zero. 相似文献
12.
The longest path problem is a well-known NP-hard problem and so far it has been solved polynomially only for a few classes of graphs. In this paper, we give a linear-time algorithm for finding a longest path between any two given vertices in a rectangular grid graph. 相似文献
13.
We generalize a known sufficient condition for the traceability of a graph to a condition for the existence of a spanning tree with a bounded number of leaves. Both of the conditions involve neighborhood unions. Further, we present two results on spanning spiders (trees with a single branching vertex). We pose a number of open questions concerning extremal spanning trees. 相似文献
14.
The neighborhood degree list (NDL) is a graph invariant that refines information given by the degree sequence and joint degree matrix of a graph and is useful in distinguishing graphs having the same degree sequence. We show that the space of realizations of an NDL is connected via a switching operation. We then determine the NDLs that have a unique realization by a labeled graph; the characterization ties these NDLs and their realizations to the threshold graphs and difference graphs. 相似文献
15.
F. Göring 《Discrete Mathematics》2010,310(9):1491-1494
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. 相似文献
16.
A graph G is perfectly orderable, if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (H, <) of (G, <). A graph is a threshold graph, if it contains no P4, 2K2, and C4 as induced subgraph. A theorem of Chvátal, Hoàng, Mahadev, and de Werra states that a graph is perfectly orderable, if it is the union of two threshold graphs. In this article, we investigate possible generalizations of the above theorem. Hoàng has conjectured that, if G is the union of two graphs G1 and G2, then G is perfectly orderable whenever G1 and G2 are both P4‐free and 2K2‐free. We show that the complement of the chordless cycle with at least five vertices cannot be a counter‐example to this conjecture, and we prove a special case of it: if G1 and G2 are two edge‐disjoint graphs that are P4‐free and 2K2‐free, then the union of G1 and G2 is perfectly orderable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 32–43, 2000 相似文献
17.
Andrzej Szepietowski 《Applied mathematics and computation》2010,217(6):2827-2832
In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AGn is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AGn − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AGn is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AGn − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AGn is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic. 相似文献
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.
20.
The Kneser graph K(n, k) has as its vertex set all k‐subsets of an n‐set and two k‐subsets are adjacent if they are disjoint. The odd graph Ok is a special case of Kneser graph when n = 2k + 1. A long standing conjecture claims that Ok is hamiltonian for all k>2. We show that the prism over Ok is hamiltonian for all k even. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:177‐188, 2011 相似文献