共查询到19条相似文献,搜索用时 228 毫秒
1.
2.
不包含2K_2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K_2并且不同构与K_2,P_3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryjá(?)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法. 相似文献
3.
设G是一个2-连通赋权图,且G中每一对不相邻顶点u和v都满足d~w(u)+d~w(v)≥2d.Bondy等人证明了G或者包含一个哈密尔顿圈,或者包含一个权至少为2d的圈.如果G不是哈密尔顿图,这个结论意味着G中包含一个权至少为2d的圈.但是当G是哈密尔顿图时,我们不能判断G是否包含一个权至少为2d的圈.这篇文章中,在Fujisawa的一篇文章的启发下,我们证明了当G是triangle-free图并且|V(G)|是奇数时,G中一定包含一个权至少为2d的圈,即使G是哈密尔顿图. 相似文献
4.
利用收缩技术,证明了1)阶为n=2k且最小半度至少是k的有向图D是强哈密尔顿连通的,除非D属于某些图类;2)2强连通且包含n个顶点、(n-1)(n-2)+4条弧的有向图是强哈密尔顿连通的,除非D属于某些图类. 相似文献
5.
图G中同构于K1,p的子图叫G的p-爪(p3).如果G中任意一个p-爪中1度顶点之间边的数目p-2,则称G为K1,p-受限图,它是无爪图(p=3时)的推广.本文证明了:连通、局部3-连通的K1,4-受限图是路可扩的. 相似文献
6.
研究子图的度和图的哈密尔顿性的关系,证明图~$G$ 是一个~$n$ 阶~3-\,连通无爪图且最小度~$\delta(G)\geq4$, 如果图~$G$ 中任意两个分别同构于~$P_4$, $K_1$ 的不相邻子图~$H_1$, $H_2$ 满足~$d(H_1)+d(H_2)\geq n$, 则图~$G$ 是哈密尔顿连通. 相似文献
7.
8.
徐新萍 《数学的实践与认识》2009,39(10)
设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果. 相似文献
9.
本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立. 相似文献
10.
11.
We introduce a new class of graphs which we call P
3-dominated graphs. This class properly contains all quasi-claw-free graphs, and hence all claw-free graphs. Let G be a 2-connected P
3-dominated graph. We prove that G is hamiltonian if α(G
2) ≤ κ(G), with two exceptions: K
2,3 and K
1,1,3. We also prove that G is hamiltonian, if G is 3-connected and |V(G)| ≤ 5δ(G) − 5. These results extend known results on (quasi-)claw-free graphs.
This paper was completed when both authors visited the Center for Combinatorics, Nankai University, Tianjin. They gratefully
acknowledge the hospitality and support of the Center for Combinatorics and Nankai University. The work of E.Vumar is sponsored
by SRF for ROCS, REM. 相似文献
12.
As an extension of quasi claw-free graphs, the class of P 3-dominated graphs has been introduced by Broersma and Vumar (Math Methods Oper Res 69:297–306, 2009). For a noncomplete graph G, the number NC and NC 2 are defined as \({NC=\min\{|N(x)\cup N(y)|: x,y\in V(G) {\rm and} xy\notin E(G)\}\, {\rm and} NC_2=\min\{|N(x)\cup N(y)|: x,y\in V(G)\, {\rm and}\, d(x,y)=2 \}}\) , respectively. For a complete graph G, set \({NC=NC_{2}=|V(G)|-1}\) . In this paper, we prove that a 2-connected P 3-dominated graph of order n is traceable if \({NC\geq (n-2)/2}\) . Moreover, we prove that a 3-connected P 3-dominated graph of order n is hamiltonian if \({NC_2\geq (2n-6)/3}\) . Our results extend some previous results on claw-free graphs. 相似文献
13.
Brendan D. McKay 《Journal of Graph Theory》2017,85(1):7-11
A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices. 相似文献
14.
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. 相似文献
15.
Saieed Akbari Hadi Alizadeh Tınaz Ekim Didem Gözüpek Mordechai Shalom 《Discrete Mathematics》2018,341(10):2859-2871
A graph is equimatchable if all of its maximal matchings have the same size. A graph is claw-free if it does not have a claw as an induced subgraph. In this paper, we provide the first characterization of claw-free equimatchable graphs by identifying the equimatchable claw-free graph families. This characterization implies an efficient recognition algorithm. 相似文献
16.
17.
Broersma and Veldman proved that every 2-connected claw-free and P 6-free graph is hamiltonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P 6-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P 6-o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P 6 of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results. 相似文献
18.
Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs 下载免费PDF全文
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. 相似文献
19.
《Journal of Graph Theory》2018,87(4):526-535
A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14]. 相似文献