共查询到20条相似文献,搜索用时 15 毫秒
1.
An edge of a k-connected graph is said to be a k-contractible edge, if its contraction yields again a k-connected graph. A noncomplete k-connected graph possessing no k-contractible edges is called contraction critical k-connected. Recently, Kriesell proved that every contraction critical 7-connected graph has two distinct vertices of degree
7. And he guessed that there are two vertices of degree 7 at distance one or two. In this paper, we give a proof to his conjecture.
The work partially supported by NNSF of China(Grant number: 10171022) 相似文献
2.
3.
4.
An edge e in a simple 3-connected graph is deletable (simple-contractible) if the deletion G\e (contraction G/e) is both simple and 3-connected. Suppose a, b, and c are three non-negative integers. If there exists a simple 3-connected graph with exactly a edges which are deletable but not simple-contractible, exactly b edges which are simple-contractible but not deletable, and exactly c edges which are both deletable and simple-contractible, then we call the triple (a, b, c) realizable, and such a graph is said to be an (a, b, c)-graph. Tutte's Wheels Theorem says the only (0, 0, 0)-graphs are the wheels. In this paper, we characterize the (a, b, c) realizable triples for which at least one of a + b≤2, c=0, and c≥16 holds.
Received: February 12, 1997 Revised: February 13, 1998 相似文献
5.
6连通图中的可收缩边 总被引:4,自引:0,他引:4
Kriesell(2001年)猜想:如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边.本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点,由此推出该猜想对κ=6成立。 相似文献
6.
Kyo Fujita 《Graphs and Combinatorics》2002,18(3):447-478
We show that if G is a 3-connected hamiltonian graph of order at least 5, then there exists a hamiltonian cycle C of G such that the number of contractible edges of G which are on C is greater than or equal to .
Received: July 31, 2000 Final version received: December 12, 2000
Acknowledgments. I would like to thank Professor Yoshimi Egawa for the help he gave to me during the preparation of this paper. 相似文献
7.
8.
Yuxing Liu 《Graphs and Combinatorics》2010,26(1):119-131
Let G be a simple 3-connected graph. An edge e of G is essential if neither the deletion G\ e nor the contraction G/e is both simple and 3-connected. In this study, we show that all 3-connected graphs with k(k ≥ 2) non-essential edges can be obtained from a wheel by three kinds of operations which defined in the paper. 相似文献
9.
10.
The 3-Connected Graphs with Exactly Three Non-Essential Edges 总被引:1,自引:0,他引:1
An edge e of a simple 3-connected graph G is essential if neither the deletion G\e nor the contraction G/e is both simple and 3-connected. Tuttes Wheels Theorem proves that the only simple 3-connected graphs with no non-essential edges are the wheels. In earlier work, as a corollary of a matroid result, the authors determined all simple3-connected graphs with at most two non-essential edges. This paper specifies all such graphs with exactly three non-essential edges. As a consequence, with the exception of the members of 10 classes of graphs, all 3-connected graphs have at least four non-essential edges.Acknowledgments The first author was partially supported by grants from the National Security Agency. The second author was partially supported by the Office of Naval Research under Grant No. N00014-01-1-0917.1991 Mathematics Subject Classification: 05C40Final version received: October 30, 2003 相似文献
11.
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. 相似文献
12.
We verify two special cases of Thomassen’s conjecture of 1976 stating that every longest cycle in a 3-connected graph contains a chord.We prove that Thomassen’s conjecture is true for two classes of 3-connected graphs that have a bounded number of removable edges on or off a longest cycle. Here an edge e of a 3-connected graph G is said to be removable if G – e is still 3-connected or a subdivision of a 3-connected (multi)graph.We give examples to showthat these classes are not covered by previous results. 相似文献
13.
Let r, t, and v be positive integers with 2 ? t ? v. For a fixed graph G with t vertices, denote by Г (r, v, G) the class of all v-partite graphs H with vertex classes Vi, |Vi| = r (i =1, 2, ... , v) satisfying the following condition: For every t-subset {i1, i2, ... , it} of {1, 2, ... , v} there exists a subgraph of H isomorphic to G having exactly one vertex in each of the classes Viτ, τ =1, 2, ... , t. Let cl(H) denote the clique number of H, i.e. the maximum order of a complete subgraph of H. We are interested in determining the value of the class parameter The main result is given the form of a Ramsey-type theorem (see Theorem 2.2). We shall show that for fixed r and G, D (r, v, G) tends to infinity when v tends to infinity if and only if χ(G) (the chromatic number of G) is greater than r. Some results concerning D(r, v, Kt), where Kt, is the complete graph on t vertices, are also given. 相似文献
14.
Let G=(I
n
,E) be the graph of the n-dimensional cube. Namely, I
n
={0,1}
n
and [x,y]∈E whenever ||x−y||1=1. For A⊆I
n
and x∈A define h
A
(x) =#{y∈I
n
A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I
n
of size 2
n−1
we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices.
Received: January 7, 2000
RID="*"
ID="*" Supported in part by BSF and by the Israeli academy of sciences 相似文献
15.
Removable Edges in Longest Cycles of 4-Connected Graphs 总被引:3,自引:0,他引:3
Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph G–e; second, for all vertices x of degree 3 in G–e, delete x from G–e and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by Ge. If Ge is 4-connected, then e is called a removable edge of G. In this paper we obtain some results on removable edges in a longest cycle of a 4-connected graph G. We also show that for a 4-connected graph G of minimum degree at least 5 or girth at least 4, any edge of G is removable or contractible.Acknowledgment. The authors are greatly indebted to a referee for his valuable suggestions and comments, which are very helpful to improve the proof of our main result Lemma 3.3.Research supported by National Science Foundation of China AMS subject classification (2000): 05C40, 05C38, 05C75Final version received: March 10, 2004 相似文献
16.
It is proved that if G is a k-connected graph which does not contain K4−, then G has an induced cycle C such that G – V(C) is (k − 2)-connected and either every edge of C is k-contractible or C is a triangle. This theorem is a generalization of some known theorems. 相似文献
17.
Matthias Kriesell 《Graphs and Combinatorics》2002,18(1):1-30
The aim of the present paper is to survey old and recent results on contractible edges in graphs of a given vertex connectivity.
Received: June 5, 2001 Final version received: August 23, 2001 相似文献
18.
19.
Rainbow Connection in 3-Connected Graphs 总被引:2,自引:0,他引:2
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we proved that rc(G) ≤ 3(n + 1)/5 for all 3-connected graphs. 相似文献
20.
For a (molecular) graph, the first Zagreb index M 1 is equal to the sum of squares of the vertex degrees, and the second Zagreb index M 2 is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we show that all connected graphs with n vertices and k cut edges, the maximum (resp. minimum) M 1- and M 2-value are obtained, respectively, and uniquely, at K n k (resp. P n k ), where K n k is a graph obtained by joining k independent vertices to one vertex of K n?k and P n k is a graph obtained by connecting a pendent path P k+1 to one vertex of C n?k. 相似文献