首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
For a graph G, let σk(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ2(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ3(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ3(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ4(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.  相似文献   

2.
A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k*-container if the set of the vertices of all the paths in C(u,v) contains all the vertices of G. A graph G is k*-connected if there exists a k*-container between any two distinct vertices. Therefore, a graph is 1*-connected (respectively, 2*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k*-connected graphs.  相似文献   

3.
A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v1,…,vk, there is a path P in G joining a and b and passing through all of v1,…,vk. A graph G is said to have property C(k) if given any k distinct vertices v1,…,vk, there is a cycle C in G containing all of v1,…,vk. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).  相似文献   

4.
In this paper we survey results of the following type (known as closure results). Let P be a graph property, and let C(u,v) be a condition on two nonadjacent vertices u and v of a graph G. Then G+uv has property P if and only if G has property P. The first and now well-known result of this type was established by Bondy and Chvátal in a paper published in 1976: If u and v are two nonadjacent vertices with degree sum n in a graph G on n vertices, then G+uv is hamiltonian if and only if G is hamiltonian. Based on this result, they defined the n-closure cln (G) of a graph G on n vertices as the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree sum n until no such pair remains. They showed that cln(G) is well-defined, and that G is hamiltonian if and only if cln(G) is hamiltonian. Moreover, they showed that cln(G) can be obtained by a polynomial algorithm, and that a Hamilton cycle in cln(G) can be transformed into a Hamilton cycle of G by a polynomial algorithm. As a consequence, for any graph G with cln(G)=K n (and n≥3), a Hamilton cycle can be found in polynomial time, whereas this problem is NP-hard for general graphs. All classic sufficient degree conditions for hamiltonicity imply a complete n-closure, so the closure result yields a common generalization as well as an easy proof for these conditions. In their first paper on closures, Bondy and Chvátal gave similar closure results based on degree sum conditions for nonadjacent vertices for other graph properties. Inspired by their first results, many authors developed other closure concepts for a variety of graph properties, or used closure techniques as a tool for obtaining deeper sufficiency results with respect to these properties. Our aim is to survey this progress on closures made in the past (more than) twenty years. Revised: September 27, 1999  相似文献   

5.
A set S of vertices in a graph G is a dominating set of G if every vertex of V(G)?S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ(G). Let Pn and Cn denote a path and a cycle, respectively, on n vertices. Let k1(F) and k2(F) denote the number of components of a graph F that are isomorphic to a graph in the family {P3,P4,P5,C5} and {P1,P2}, respectively. Let L be the set of vertices of G of degree more than 2, and let GL be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd [W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n≥8 with δ(G)≥2, then γ(G)≤2n/5, while Reed [B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ(G)≥3, then γ(G)≤3n/8. As an application of Reed’s result, we show that if G is a graph of order n≥14 with δ(G)≥2, then .  相似文献   

6.
We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K5E(C4), where C4 is an cycle of length 4 in K5) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.  相似文献   

7.
A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u 1 = v 1, v = u v(G) = v v(G) , and u i ≠ v i for every 1 < iv(G). A set of hamiltonian paths, {P 1, P 2, . . . , P k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with nk ≥ 2. We use S n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S n,k ) = n–2 except for S 4,2 such that IHP(S 4,2) = 1.   相似文献   

8.
 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s 3(G) ≥ 2 k −3, where s r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s 3(G) < 2 k −2, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000  相似文献   

9.
By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then Hn,k, the graph obtained from the star K1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.  相似文献   

10.
A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every FE(G) with |F|=k, GF is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either GKk+2,k+2, or k=4r−2 for some integer r≥3 and GC5[N2r], where N2r is the empty graph on 2r vertices and C5[N2r] is the graph obtained from C5 by replacing each vertex with a graph isomorphic to N2r.  相似文献   

11.
The generalised Ramsey number R(G1, G2,..., Gk) is defined as the smallest integer n such that, if the edges of Kn, the complete graph on n vertices, are coloured using k colours C1, C2,..., Ck, then for some i(1≤ik) there is a subgraph Gi of Kn with all of its edges colour Ci. When G1=G2=...,Gk=G, we use the more compact notation Rk(G).The generalised Ramsey numbers Rk(G) are investigated for all graphs G having at most four vertices (and no isolates). This extends the work of Chvátal and Harary, who made this investigation in the case k=2.  相似文献   

12.
The kth power of a cycle C is the graph obtained from C by joining every pair of vertices with distance at most k on C. The second power of a cycle is called a square cycle. Pósa conjectured that every graph with minimum degree at least 2n/3 contains a hamiltonian square cycle. Later, Seymour proposed a more general conjecture that if G is a graph with minimum degree at least (kn)/(k + 1), then G contains the kth power of a hamiltonian cycle. Here we prove an Ore-type version of Pósa’s conjecture that if G is a graph in which deg(u) + deg(v) ≥ 4n/3 ? 1/3 for all non-adjacent vertices u and v, then for sufficiently large n, G contains a hamiltonian square cycle unless its minimum degree is exactly n/3 + 2 or n/3 + 5/3. A consequence of this result is an Ore-type analogue of a theorem of Aigner and Brandt.  相似文献   

13.
The stable Kneser graph SGn,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K2,SGn,k)?Sk. The dihedral group D2m acts canonically on SGn,k, the group C2 with 2 elements acts on K2. We almost determine the (C2×D2m)-homotopy type of Hom(K2,SGn,k) and use this to prove the following results.The graphs SG2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SGn,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SGn,k,G) is (r−1)-connected and χ(G)<r+k+2.  相似文献   

14.
Let G(n, k) denote the graph of the Johnson Scheme J(n, k), i.e., the graph whose vertices are all k-subsets of a fixed n-set, with two vertices adjacent if and only if their intersection is of size k ? 1. It is known that G(n, k) is a distance regular graph with diameter k. Much work has been devoted to the question of whether a distance regular graph with the parameters of G(n, k) must isomorphic to G(n, k). In this paper, this question is settled affirmatively for n ≥ 20. In fact the result is proved with weaker conditions.  相似文献   

15.
The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ 2(G):=min?{d(u)+d(v)|uv ? E(G),uv}. In the paper, the main results of this paper are as follows:
  1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ 2(G)≥n+2k?2, then for any set of k distinct vertices v 1,…,v k , G has k vertex-disjoint cycles C 1,C 2,…,C k of length at most four such that v i V(C i ) for all 1≤ik.
  2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ 2(G)≥n+2k?2, then for any set of k distinct vertices v 1,…,v k , G has k vertex-disjoint cycles C 1,C 2,…,C k such that:
    1. v i V(C i ) for all 1≤ik.
    2. V(C 1)∪???V(C k )=V(G), and
    3. |C i |≤4, 1≤ik?1.
Moreover, the condition on σ 2(G)≥n+2k?2 is sharp.  相似文献   

16.
For k?0, ?k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?k(G–e)<?k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order.  相似文献   

17.
For an ordered set W = {w 1, w 2,..., w k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w 1), d(v, w 2),... d(v, w k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K n or G = K 1,n?1. It is also shown that for positive integers a, b with ab, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K 2 for connected graphs G are studied.  相似文献   

18.
Path graphs     
The concept of a line graph is generalized to that of a path graph. The path graph Pk(G) of a graph G is obtained by representing the paths Pk in G by vertices and joining two vertices whenever the corresponding paths Pk in G form a path Pk+1 or a cycle Ck. P3-graphs are characterized and investigated on isomorphism and traversability. Trees and unicyclic graphs with hamiltonian P3-graphs are characterized.  相似文献   

19.
A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most and, for n?6, the only HPS graph of order n and size is Kn-1K1. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)?⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n?54, an HPS graph Gn of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)?⌊(3n-1)/2⌋ for n?54. We also consider m-path cover saturated graphs and Pm-saturated graphs with small size.  相似文献   

20.
Zeev Nutov 《Discrete Mathematics》2008,308(12):2533-2543
Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph Kk,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)2/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.  相似文献   

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

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