共查询到20条相似文献,搜索用时 93 毫秒
1.
2.
3.
本文证明了下列结论:设G是p阶3-连通无爪简单图。若对于G中任意3个顶点的独立集{x1,x2,x3},有 d(x1)+d(x2)+d(x3)≥p+1 则G是Hamilton-连通图。 相似文献
4.
1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的. 相似文献
5.
6.
7.
8.
9.
10.
本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立. 相似文献
11.
A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound. 相似文献
12.
A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC(G),is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC(G) and characterize the extremal graphs achieving the lower bound for a connected(claw,K4)-free 4-regular graph G.Furthermore,we show that for any 2-connected(claw,K4)-free 4-regular graph G of order n,its clique-transversal number equals to [n/3]. 相似文献
13.
A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by τ
c
(G), is the minimum cardinality of a clique-transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we
give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving
the lower bound. 相似文献
14.
P. Dankelmann Henda C. Swart P. van den Berg W. Goddard M. D. Plummer 《Czechoslovak Mathematical Journal》2008,58(3):787-798
A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K
1,3 (claw) as an induced subgraph and if, for each edge e of G, G ™ e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees
of their vertices, and characterize graphs which have m.c.f. line graphs.
Support by the South African National Research Foundation is gratefully acknowledged. 相似文献
15.
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 相似文献
16.
XuXinping 《高校应用数学学报(英文版)》2005,20(1):121-126
Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U V(G) ,let N(U)=Uu,∈UN(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K1.3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al. : Let G be a 2-connected claw-free graph of order n,and d(u) d(v) d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s ,t and w,such that if G is a (s t w-1)connected claw-free graph of order n,and d(S) d(T) d(W)>n-(s t w) for every three disjoint independent vertex sets S,T,W with |S |=s, |T|=t, |W|=w,and S∪T∪W is also independent ,then G is Hamiltonian. Other related results are obtained too. 相似文献
17.
The smallest number of cliques, covering all edges of a graph , is called the (edge) clique cover number of and is denoted by . It is an easy observation that if is a line graph on vertices, then . G. Chen et al. [Discrete Math. 219 (2000), no. 1–3, 17–26; MR1761707] extended this observation to all quasi-line graphs and questioned if the same assertion holds for all claw-free graphs. In this paper, using the celebrated structure theorem of claw-free graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all claw-free graphs with independence number at least three. In particular, we prove that if is a connected claw-free graph on vertices with three pairwise nonadjacent vertices, then and the equality holds if and only if is either the graph of icosahedron, or the complement of a graph on vertices called “twister” or the power of the cycle , for some positive integer . 相似文献
18.
19.
Akira Kamibeppu 《Discrete Applied Mathematics》2010,158(2):154-157
A hole of a graph is an induced cycle of length at least 4. Kim (2005) [2] conjectured that the competition number k(G) is bounded by h(G)+1 for any graph G, where h(G) is the number of holes of G. In Lee et al. [3], it is proved that the conjecture is true for a graph whose holes are mutually edge-disjoint. In Li et al. (2009) [4], it is proved that the conjecture is true for a graph, all of whose holes are independent. In this paper, we prove that Kim’s conjecture is true for a graph G satisfying the following condition: for each hole C of G, there exists an edge which is contained only in C among all induced cycles of G. 相似文献
20.
In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217–224). For a claw-free graph G and its closure cl(G), we prove: (1) V(G) is covered by k cycles in G if and only if V(cl(G)) is covered by k cycles of cl(G); and (2) G has a 2-factor with at most k components if and only if cl(G) has a 2-factor with at most k components. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 109–117, 1999 相似文献