共查询到20条相似文献，搜索用时 15 毫秒
1.
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 相似文献
2.
Gábor Wiener 《Journal of Graph Theory》2017,84(4):443-459
The minimum leaf number ml(G) of a connected graph G is defined as the minimum number of leaves of the spanning trees of G if G is not hamiltonian and 1 if G is hamiltonian. We study nonhamiltonian graphs with the property for each or for each . These graphs will be called ‐leaf‐critical and l‐leaf‐stable, respectively. It is far from obvious whether such graphs exist; for example, the existence of 3‐leaf‐critical graphs (that turn out to be the so‐called hypotraceable graphs) was an open problem until 1975. We show that l‐leaf‐stable and l‐leaf‐critical graphs exist for every integer , moreover for n sufficiently large, planar l‐leaf‐stable and l‐leaf‐critical graphs exist on n vertices. We also characterize 2‐fragments of leaf‐critical graphs generalizing a lemma of Thomassen. As an application of some of the leaf‐critical graphs constructed, we settle an open problem of Gargano et al. concerning spanning spiders. We also explore connections with a family of graphs introduced by Grünbaum in correspondence with the problem of finding graphs without concurrent longest paths. 相似文献
3.
A poset P=(X,P) is a split semiorder when there exists a function I thatassigns to each x X a closed interval
of the real line R and a set
of real numbers, with
, suchthat x<y in P if and only if
and
in R. Every semiorder is a split semiorder, and thereare split semiorders which are not interval orders. It is well known thatthe dimension of a semiorder is at most 3. We prove that the dimension of asplit semiorder is at most 6. We note also that some split semiorders havesemiorder dimension at least 3, and that every split semiorder has intervaldimension at most 2. 相似文献
4.
Joel Foisy 《Journal of Graph Theory》2003,42(3):199-210
For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003 相似文献
5.
Let G be a connected claw-free graph on n vertices. Let ς3(G) be the minimum degree sum among triples of independent vertices in G. It is proved that if ς3(G) ≥ n − 3 then G is traceable or else G is one of graphs Gn each of which comprises three disjoint nontrivial complete graphs joined together by three additional edges which induce a triangle K3. Moreover, it is shown that for any integer k ≥ 4 there exists a positive integer ν(k) such that if ς3(G) ≥ n − k, n > ν(k) and G is non-traceable, then G is a factor of a graph Gn. Consequently, the problem HAMILTONIAN PATH restricted to claw-free graphs G = (V, E) (which is known to be NP-complete) has linear time complexity O(|E|) provided that ς3(G) ≥ . This contrasts sharply with known results on NP-completeness among dense graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 75–86, 1998 相似文献
6.
研究了在含有故障点和（或）故障边的n维超立方体Qn中经过给定路的无故障圈问题,得到以下结果：设Fv V（Qn）,Fe E（Qn）.若｜Fv｜＋｜Fe｜≤n-h且3≤h≤n,或｜Fv｜＋｜Fe｜≤n-3且h=2,则在Qn-Fv-Fe中,每一条长度等于h的路P都包含在每个偶长度从2h＋2到2^n-2｜Fv｜的圈中.并且若又有条件｜Fv｜＋｜Fe｜〈h-1时,则路P还包含在长度等于2h的无故障的圈中. 相似文献
7.
A. Abouelaoualim K. Ch. Das W. Fernandez de la Vega M. Karpinski Y. Manoussakis C. A. Martinhon R. Saad 《Journal of Graph Theory》2010,64(1):63-86
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 相似文献
8.
9.
《Discrete Mathematics》2024,347(1):113657
A frequency n-cube is an n-dimensional q-by-...-by-q array, where , filled by numbers with the property that each line contains exactly cells with symbol i, (a line consists of q cells of the array differing in one coordinate). The trivial upper bound on the number of frequency n-cubes is . We improve that lower bound for , replacing by a smaller value s, by constructing a testing set of size for frequency n-cubes (a testing set is a collection of cells of an array the values in which uniquely determine the array with given parameters). We also construct new testing sets for generalized frequency n-cubes, which are essentially correlation-immune functions in n q-valued arguments; the cardinalities of new testing sets are smaller than for testing sets known before. 相似文献
10.
《Journal of Graph Theory》2018,87(2):164-175
In this article, we investigate the number of hamiltonian cycles in triangulations. We improve a lower bound of for the number of hamiltonian cycles in triangulations without separating triangles (4‐connected triangulations) by Hakimi, Schmeichel, and Thomassen to a linear lower bound and show that a linear lower bound even holds in the case of triangulations with one separating triangle. We confirm their conjecture about the number of hamiltonian cycles in triangulations without separating triangles for up to 25 vertices and give computational results and constructions for triangulations with a small number of hamiltonian cycles and 1–5 separating triangles. 相似文献
11.
Jozef Jirsek 《Journal of Graph Theory》2005,49(1):59-68
Locke and Witte described infinite families of nonhamiltonian circulant oriented graphs. We show that for infinitely many of them the reversal of any arc produces a hamiltonian cycle. This solves an open problem stated by Thomassen in 1987. We also use these graphs to construct counterexamples to Ádám's conjecture on arc reversal. One of them is a counterexample with the smallest known number of vertices. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 59–68, 2005 相似文献
12.
张磊 《数学的实践与认识》2020,(10):309-314
经过图的每个点恰一次的圈称为是图的Hamiltonian圈.假设G是直径为2的n阶连通图.通过研究顶点的邻域,给出一些G包含长圈的充分条件. 相似文献
13.
In this paper, we introduce the decycling number of a graph as the minimum number of vertices that must be removed in order to eliminate all cycles. After proving some general results, we focus on two families of graph products, the grids and the hypercubes. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 59–77, 1997 相似文献
14.
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 degG x+degG 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 相似文献
15.
斯钦 《数学的实践与认识》2008,38(8):151-157
图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题. 相似文献
16.
We study the hamiltonicity of certain graphs obtained from the hypercube as a means of producing a binary code of distance two and length n, whose codewords are ordered so that for each two consecutive codewords, one dominates the other. One vector dominates the other, if and only if, in all the positions where one of them has a zero, the other has a zero too. These dominated codes have applications in group testing for consecutive defectives. We also determine when the vectors can be ordered so that every two consecutive vectors have the domination property, and are at distance two; this is a natural generalization of Gray codes. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 294–302, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10012 相似文献
17.
In [3] a certain family of topological spaces was introduced on ultraproducts. These spaces have been called ultratopologies and their definition was motivated by model theory of higher order logics. Ultratopologies provide a natural extra topological structure for ultraproducts. Using this extra structure in [3] some preservation and characterization theorems were obtained for higher order logics. The purely topological properties of ultratopologies seem interesting on their own right. We started to study these properties in [2], where some questions remained open. Here we present the solutions of two such problems. More concretely we show 1. that there are sequences of finite sets of pairwise different cardinalities such that in their certain ultraproducts there are homeomorphic ultratopologies and 2. if A is an infinite ultraproduct of finite sets, then every ultratopology on A contains a dense subset D such that |D| < |A|. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
18.
19.
Let FF_v be the set of faulty nodes in an n-dimensional folded hypercube FQ_n with |FF_v| ≤ n-1 and all faulty vertices are not adjacent to the same vertex. In this paper, we show that if n ≥ 4, then every edge of FQn-FF_v lies on a fault-free cycle of every even length from 6 to 2~n-2|FF_v|. 相似文献
20.
Herbert Fleischner 《Journal of Graph Theory》2014,75(2):167-177
We construct an infinite family of uniquely hamiltonian graphs of minimum degree 4, maximum degree 14, and of arbitrarily high maximum degree. 相似文献