首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
Hao Li  Weihua Yang 《Discrete Mathematics》2012,312(24):3670-3674
Thomassen conjectured that every 4-connected line graph is Hamiltonian. Lai et al. (in 2006) [5] considered whether the high essential connectivity of the 3-connected line graphs can guarantee the existence of the Hamiltonian cycle in graphs and they showed that every 3-connected, essentially 11-connected line graph is Hamiltonian. In this note, we show that every 3-connected, essentially 10-connected line graph is Hamiltonian-connected. The result strengthens the known result mentioned above.  相似文献   

2.
Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K5-E(C4), where C4 is a cycle of length 4 in K5. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.  相似文献   

3.
Lai, Shao and Zhan (J Graph Theory 48:142–146, 2005) showed that every 3-connected N 2-locally connected claw-free graph is Hamiltonian. In this paper, we generalize this result and show that every 3-connected claw-free graph G such that every locally disconnected vertex lies on some induced cycle of length at least 4 with at most 4 edges contained in some triangle of G is Hamiltonian. It is best possible in some sense.  相似文献   

4.
Thomassen conjectured in 1986 that every 4-connected line graph is hamiltonian. In this paper, we show that 6-connected line graphs are hamiltonian, improving on an analogous result for 7-connected line graphs due to Zhan in 1991. Our result implies that every 6-connected claw-free graph is hamiltonian.  相似文献   

5.
A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained.  相似文献   

6.
The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995 that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d G (u) + d G (v) ≥ 9, then G has a spanning eulerian subgraph.  相似文献   

7.
We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is Hamiltonian), by Thomassen (every 4-connected line graph is Hamiltonian) and by Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent to the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.We use a refinement of the contractibility technique which was introduced by Ryjá?ek and Schelp in 2003 as a common generalization and strengthening of the reduction techniques by Catlin and Veldman and of the closure concept introduced by Ryjá?ek in 1997.  相似文献   

8.
A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper Finbow et al. (2004) [3] that there are no 5-connected planar well-covered triangulations, and in Finbow et al. (submitted for publication) [4] that there are exactly four 4-connected well-covered triangulations containing two adjacent vertices of degree 4. It is the aim of the present paper to complete the characterization of 4-connected well-covered triangulations by showing that each such graph contains two adjacent vertices of degree 4.  相似文献   

9.
不包含2K_2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K_2并且不同构与K_2,P_3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryjá(?)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.  相似文献   

10.
DP-coloring as a generalization of list coloring was introduced by Dvořák and Postle in 2017, who proved that every planar graph without cycles from 4 to 8 is 3-choosable, which was conjectured by Borodin et al. in 2007. In this paper, we prove that every planar graph without adjacent cycles of length at most 8 is 3-choosable, which extends this result of Dvořák and Postle.  相似文献   

11.
In the present paper we show that if G is a 2-connected claw-free graph such that the vertices of degree 1 of every induced bull have a common neighbour in G then G is hamiltonian. This statement was originally conjectured by H.J. Broersma and H.J. Veldman  相似文献   

12.
Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z 3-flow and Jaeger et al. [Group connectivity of graphs–a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B 56 (1992) 165-182] further conjectured that every 5-edge-connected graph is Z 3-connected. These two conjectures are in general open and few results are known so far. A weaker version of Tutte’s conjecture states that every 4-edge-connected graph with each edge contained in a circuit of length at most 3 admits a nowhere-zero Z 3-flow. Devos proposed a stronger version problem by asking if every such graph is Z 3-connected. In this paper, we first answer this later question in negative and get an infinite family of such graphs which are not Z 3-connected. Moreover, motivated by these graphs, we prove that every 6-edge-connected graph whose edge set is an edge disjoint union of circuits of length at most 3 is Z 3-connected. It is a partial result to Jaeger’s Z 3-connectivity conjecture. Received: May 23, 2006. Final version received: January 13, 2008  相似文献   

13.
A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least (|V(G)|-2)/3. At the workshop C&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if each end-vertex of every induced copy of H in G has degree at least |V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.  相似文献   

14.
Summary A variety of examples of 4-connected 4-regular graphs with no pair of disjoint Hamiltonian circuits were constructed in response to Nash-Williams conjecture that every 4-connected 4-regular graph is Hamiltonian and also admits a pair of edge-disjoint Hamiltonian circuits. Nash-Williams's problem is especially interesting for planar graphs since 4-connected planar graphs are Hamiltonian. Examples of 4-connected 4-regular planar graphs in which every pair of Hamiltonian circuits have edges in common are included in the above mentioned examples.B. Grünbaum asked whether 5-connected planar graphs always admit a pair of disjoint Hamiltonian circuits. In this paper we introduce a technique that enables us to construct infinitely many examples of 5-connected planar graphs, 5-regular and non regular, in which every pair of Hamiltonian circuits have edges in common.  相似文献   

15.
16.
Let Δ denote the maximum degree of a graph. Fiam?ík first and then Alon et al. again conjectured that every graph is acyclically edge (Δ+2)-colorable. Even for planar graphs, this conjecture remains open. It is known that every triangle-free planar graph is acyclically edge (Δ+5)-colorable. This paper proves that every planar graph without intersecting triangles is acyclically edge (Δ+4)-colorable.  相似文献   

17.
A one-way infinite Hamiltonian path is constructed in an infinite 4-connected VAP-free maximal planar graph containing one or two vertices of infinite degree. Combining this result and that of R. HALIN who investigated the structure of such graphs, we conclude that such a path always exists in every infinite 4-connected maximal planar graph with exactly one end, which is an extension of H. WHITNEY'S theorem to infinite graphs.  相似文献   

18.
覃城阜  郭晓峰 《数学研究》2011,44(3):243-256
M.Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10.本文构造了一个反例证明M.Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界.  相似文献   

19.
Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al. 2002) [7]. This conjecture if proved would imply both Borodin’s acyclic 5-color theorem (1979) and Thomassen’s 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs.Some sufficient conditions are also obtained for a planar graph to be acyclically 4-choosable and 3-choosable. In particular, acyclic 4-choosability was proved for the following planar graphs: without 3-cycles and 4-cycles (Montassier, 2006 [23]), without 4-cycles, 5-cycles and 6-cycles (Montassier et al. 2006 [24]), and either without 4-cycles, 6-cycles and 7-cycles, or without 4-cycles, 6-cycles and 8-cycles (Chen et al. 2009 [14]).In this paper it is proved that each planar graph with neither 4-cycles nor 6-cycles adjacent to a triangle is acyclically 4-choosable, which covers these four results.  相似文献   

20.
 A. Saito conjectured that every finite 3-connected line graph of diameter at most 3 is hamiltonian unless it is the line graph of a graph obtained from the Petersen graph by adding at least one pendant edge to each of its vertices. Here we shall see that a line graph of connectivity 3 and diameter at most 3 has a hamiltonian path. Received: May 31, 2000 Final version received: August 17, 2001 RID="*" ID="*" This work has partially been supported by DIMATIA, Grant 201/99/0242, Grant Agency of the Czech Republic AMS subject classification: 05C45, 05C40  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号