共查询到20条相似文献,搜索用时 250 毫秒
1.
An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K6. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K6 by a number of θ+-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either Kk+1 or the graph Hk/2+1 obtained from Kk+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to Kk+1. 相似文献
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.
《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.
We combine two well-known results by Mader and Thomassen, respectively. Namely, we prove that for any k-connected graph G (k≥4), there is an induced cycle C such that G−V(C) is (k−3)-connected and G−E(C) is (k−2)-connected. Both “(k−3)-connected” and “(k−2)-connected” are best possible in a sense. 相似文献
5.
Degree conditions for group connectivity 总被引:1,自引:0,他引:1
Let G be a 2-edge-connected simple graph on n≥13 vertices and A an (additive) abelian group with |A|≥4. In this paper, we prove that if for every uv∉E(G), max{d(u),d(v)}≥n/4, then either G is A-connected or G can be reduced to one of K2,3,C4 and C5 by repeatedly contracting proper A-connected subgraphs, where Ck is a cycle of length k. We also show that the bound n≥13 is the best possible. 相似文献
6.
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. 相似文献
7.
An edge e of a k-connected graph G is said to be k-contractible (or simply contractible) if the graph obtained from G by contracting e (i.e., deleting e and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still k-connected. In 2002, Kawarabayashi proved that for any odd integer k ? 5, if G is a k-connected graph and G contains no subgraph D = K 1 + (K 2 ∪ K 1,2), then G has a k-contractible edge. In this paper, by generalizing this result, we prove that for any integer t ? 3 and any odd integer k ? 2t + 1, if a k-connected graph G contains neither K 1 + (K 2 ∪ K 1,t ), nor K 1 + (2K 2 ∪ K 1,2), then G has a k-contractible edge. 相似文献
8.
A graph G is dot-critical if contracting any edge decreases the domination number. Nader Jafari Rad (2009) [3] posed the problem: Is it true that a connected k-dot-critical graph G with G′=0? is 2-connected? In this note, we give a family of 1-connected 2k-dot-critical graph with G′=0? and show that this problem has a negative answer. 相似文献
9.
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. 相似文献
10.
《European Journal of Combinatorics》2005,26(3-4):293-308
Suppose G is a k-connected graph that does not contain Kk as a minor. What does G look like? This question is motivated by Hadwiger’s conjecture (Vierteljahrsschr. Naturforsch. Ges. Zürich 88 (1943) 133) and a deep result of Robertson and Seymour (J. Combin. Theory Ser. B. 89 (2003) 43).It is easy to see that such a graph cannot contain a (k−1)-clique, but could contain a (k−2)-clique, as Kk−5+G′, where G′ is a 5-connected planar graph, shows. In this paper, however, we will prove that such a graph cannot contain three “nearly” disjoint (k−2)-cliques. This theorem generalizes some early results by Robertson et al. (Combinatorica 13 (1993) 279) and Kawarabayashi and Toft (Combinatorica (in press)). 相似文献
11.
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). 相似文献
12.
Sparse connectivity certificates via MA orderings in graphs 总被引:1,自引:0,他引:1
Hiroshi Nagamochi 《Discrete Applied Mathematics》2006,154(16):2411-2417
For an undirected multigraph G=(V,E), let α be a positive integer weight function on V. For a positive integer k, G is called (k,α)-connected if any two vertices u,v∈V remain connected after removal of any pair (Z,E′) of a vertex subset Z⊆V-{u,v} and an edge subset E′⊆E such that ∑v∈Zα(v)+|E′|<k. The (k,α)-connectivity is an extension of several common generalizations of edge-connectivity and vertex-connectivity. Given a (k,α)-connected graph G, we show that a (k,α)-connected spanning subgraph of G with O(k|V|) edges can be found in linear time by using MA orderings. We also show that properties on removal cycles and preservation of minimum cuts can be extended in the (k,α)-connectivity. 相似文献
13.
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. 相似文献
14.
An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. In this paper, we prove that a (K1 + C4)-free minimally k-connected graph has a k-contractible edge, if around each vertex of degree k, there is an edge which is not contained in a triangle. This implies previous two results, one due to Thomassen and the other due to Kawarabayashi. 相似文献
15.
A generalized matrix norm G dominates the spectral radius for all A?Mn(C) (i) if for some positive integer k the rule G(Ak) ? G(A)k holds for all A?Mn(C) and (ii) if and only if for each A?Mn(C) there exists a constant γA such that G(Ak) ? γAG(A)kfor all positive integers k. Other results and examples are also given concerning spectrally dominant generalized matrix norms. 相似文献
16.
Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, Ck(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ∗(G), is the maximum integer k such that G is w∗-connected for 1≤w≤k if G is 1∗-connected.Let x be a vertex in G and let U={y1,y2,…,yk} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, Fk(x,U), is a set of internally-disjoint paths {P1,P2,…,Pk} such that Pi is a path connecting x to yi for 1≤i≤k and . A graph G is k∗-fan-connected (or -connected) if there exists a spanning Fk(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k∗-pipeline-connected. 相似文献
17.
An edge e of a k-connected graph G is said to be k-removable if G — e is still k-connected. A subgraph H of a k-connected graph is said to be k-contractible if its contraction results still in a k-connected graph. A k-connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k-connected. In this paper, we show that there is a contractible subgraph in a 5-connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor minimally 5-connected graph is contained in some triangle. 相似文献
18.
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. 相似文献
19.
In 2001, Kawarabayashi proved that for any odd integer k ≥ 3, if a k-connected graph G is \({K^{-}_{4}}\) -free, then G has a k-contractible edge. He pointed out, by a counterexample, that this result does not hold when k is even. In this paper, we have proved the following two results on the subject: (1) For any even integer k ≥ 4, if a k-connected graph G is \({K_{4}^{-}}\) -free and d G (x) + d G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge. (2) Let t ≥ 3, k ≥ 2t – 1 be integers. If a k-connected graph G is \({(K_{1}+(K_{2} \cup K_{1, t}))}\) -free and d G (x) + d G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge. 相似文献
20.
A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree. 相似文献