共查询到20条相似文献,搜索用时 46 毫秒
1.
P.A. Sinclair 《Discrete Mathematics》2004,286(3):177-184
Let G be a connected graph with minimum degree at least 3. We prove that there exists an even circuit C in G such that G−E(C) is either connected or contains precisely two components one of which is isomorphic to a 1-bond. We further prove sufficient conditions for there to exist an even circuit C in a 2-connected simple graph G such that G−E(C) is 2-connected. As a consequence of this, we obtain sufficient conditions for there to exist an even circuit C in a 2-connected graph G for which G−E(C) is 2-connected. 相似文献
2.
Connectivity of iterated line graphs 总被引:1,自引:0,他引:1
Yehong Shao 《Discrete Applied Mathematics》2010,158(18):2081-2087
Let k≥0 be an integer and Lk(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L2(G))≥4δ(G)−6. We show that the connectivity of G can be relaxed. In fact, we prove in this note that if G is an essentially 4-edge-connected and 3-connected graph, then κ(L2(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs. 相似文献
3.
《Journal of Combinatorial Theory, Series B》1987,42(3):371-377
It is shown that for k ≥ 3, every k-connected graph G with girth at least 4 contains an induced cycle C such that G − V(C) is (k − 2)-connected. 相似文献
4.
Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C0,C1,…,Ck such that k+1<|E(C0)|<|E(C1)|<?<|E(Ck)|, |E(Ci)−E(Ci−1)|=2, 1≤i≤k−1, and 1≤|E(Ck)|−|E(Ck−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(Ck)|−|E(Ck−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if dG(u)+dG(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C0,C1,…,Ck such that k+1<|E(C0)|<|E(C1)|<?<|E(Ck)|, |E(Ci)−E(Ci−1)|=2, 1≤i≤k−1, and 1≤|E(Ck)|−|E(Ck−1)|≤2, and furthermore, if dG(u)+dG(v)≥6k+1, then |E(Ck)|−|E(Ck−1)|=2. 相似文献
5.
For a graph G let μ(G) denote the cyclomatic number and let ν(G) denote the maximum number of edge-disjoint cycles of G.We prove that for every k≥0 there is a finite set P(k) such that every 2-connected graph G for which μ(G)−ν(G)=k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k≤2 exactly. 相似文献
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 K5−E(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.
Kenta Ozeki 《Discrete Mathematics》2009,309(13):4266-4269
Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ3(G)≥n is prism hamiltonian. The degree sum condition “σ3(G)≥n” is best possible. 相似文献
8.
For a graph G, let σ2(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ2(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ2(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K2+(K2∪Kn−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ2(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible. 相似文献
9.
Suppose that a 2-connected cubic graph G of order n has a circuit C of length at least n−4 such that G−V(C) is connected. We show that G has a circuit double cover containing a prescribed set of circuits which satisfy certain conditions. It follows that hypohamiltonian cubic graphs (i.e., non-hamiltonian cubic graphs G such that G−v is hamiltonian for every v∈V(G)) have strong circuit double covers. 相似文献
10.
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. 相似文献
11.
Carsten Schultz 《Journal of Combinatorial Theory, Series A》2011,118(8):2291-2318
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. 相似文献
12.
Philip Sinclair 《Discrete Mathematics》2004,286(3):171-175
Let G be a 2-connected graph with minimum degree at least 3. We prove that there exists an even circuit C in G with factorization F={F1,F2} such that G−E(F1) is 2-connected. 相似文献
13.
Ken-ichi Kawarabayashi 《Discrete Mathematics》2010,310(20):2655-2661
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). 相似文献
14.
15.
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 it contains all vertices of G. A graph G is k*-connected if there exists a k*-container between any two distinct vertices. The spanning connectivity of G, κ*(G), is defined to be the largest integer k such that G is w*-connected for all 1?w?k if G is a 1*-connected graph. In this paper, we prove that κ*(G)?2δ(G)-n(G)+2 if (n(G)/2)+1?δ(G)?n(G)-2. Furthermore, we prove that κ*(G-T)?2δ(G)-n(G)+2-|T| if T is a vertex subset with |T|?2δ(G)-n(G)-1. 相似文献
16.
Yoshimi Egawa 《Discrete Mathematics》2009,309(6):1565-1574
For a graph G, a subset S of V(G) is called a shredder if G−S consists of three or more components. We show that if G is a 5-connected graph with |V(G)|≥135, then the number of shredders of cardinality 5 of G is less than or equal to (2|V(G)|−10)/3. 相似文献
17.
João Paulo Costalonga 《European Journal of Combinatorics》2012,33(1):72-81
Whittle proved, for k=1,2, that if N is a 3-connected minor of a 3-connected matroid M, satisfying r(M)−r(N)≥k, then there is a k-independent set I of M such that, for every x∈I, si(M/x) is a 3-connected matroid with an N-minor. In this paper, we establish this result for k=3. It is already known that it cannot be extended to greater values of k. But, here we also show that, in the graphic case, with the extra assumption that r(M)−r(N)≥6, we can guarantee the existence of a 4-independent set of M with such a property. Moreover, in the binary case, we show that if r(M)−r(N)≥5, then M has such a 4-independent set or M has a triangle T meeting 3 triads and such that M/T is a 3-connected matroid with an N-minor. 相似文献
18.
Gopal Prasad 《Advances in Mathematics》2004,181(1):160-164
We give a purely “local” proof of the fact that the topological central extension of G(k), G an absolutely almost simple algebraic group defined and isotropic over a nonarchimedean local field k, by the finite group μ(k) of roots of unity in k, constructed by Pierre Deligne, is a universal topological central extension of G(k). 相似文献
19.
Ken-ichi Kawarabayashi 《Journal of Combinatorial Theory, Series B》2011,101(4):206-213
A graph with at least 2k+2 vertices is said to be k-extendable if any independent set of k edges in it extends to a perfect matching. We shall show that every 5-connected graph G of even order embedded on a closed surface F2, except the sphere, is 2-extendable if ρ(G)?7−2χ(F2), where ρ(G) stands for the representativity of G on F2 and χ(F2) for the Euler characteristic of F2. 相似文献
20.
Ken-ichi Kawarabayashi 《Discrete Mathematics》2008,308(24):5899-5906
For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. Bondy and Locke [J.A. Bondy, S.C. Locke, Relative length of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122] consider the gap between p(G) and c(G) in 3-connected graphs G. Starting with this result, there are many results appeared in this context, see [H. Enomoto, J. van den Heuvel, A. Kaneko, A. Saito, Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory 20 (1995) 213-225; M. Lu, H. Liu, F. Tian, Relative length of longest paths and cycles in graphs, Graphs Combin. 23 (2007) 433-443; K. Ozeki, M. Tsugaki, T. Yamashita, On relative length of longest paths and cycles, preprint; I. Schiermeyer, M. Tewes, Longest paths and longest cycles in graphs with large degree sums, Graphs Combin. 18 (2002) 633-643]. In this paper, we investigate graphs G with p(G)−c(G) at most 1 or at most 2, but with no hamiltonian paths. Let G be a 2-connected graph of order n, which has no hamiltonian paths. We show two results as follows: (i) if , then p(G)−c(G)≤1, and (ii) if σ4(G)≥n+3, then p(G)−c(G)≤2. 相似文献