Vertices of Degree 5 in a Contraction Critically 5-connected Graph

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. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. We prove that a contraction critically 5-connected graph on n vertices has at least n/5 vertices of degree 5. We also show that, for a graph G and an integer k greater than 4, there exists a contraction critically k-connected graph which has G as its induced subgraph.     

The New Lower Bound of the Number of Vertices of Degree 5 in Contraction Critical 5-Connected Graphs

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. Let G be a contraction critical 5-connected graph, in this paper we show that G has at least ${\frac{1}{2}|G|}$ vertices of degree 5.     

Some structural properties of minimally contraction-critically 5-connected graphs

An edge of a k-connected graph is said to be k-removable (resp. k-contractible) if the removal (resp. the contraction ) of the edge results in a k-connected graph. A k-connected graph with neither k-removable edge nor k-contractible edge is said to be minimally contraction-critically k-connected. We show that around an edge whose both end vertices have degree greater than 5 of a minimally contraction-critically 5-connected graph, there exists one of two specified configurations. Using this fact, we prove that each minimally contraction-critically 5-connected graph on n vertices has at least vertices of degree 5.     

A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. An edge of a k-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree k. Ando [K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math. 293 (2005) 61-72] proved that a contraction critical 5-connected graph on n vertices has at least n/2 trivially noncontractible edges. Li [Xiangjun Li, Some results about the contractible edge and the domination number of graphs, Guilin, Guangxi Normal University, 2006 (in Chinese)] improved the lower bound to n+1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on n vertices has at least trivially noncontractible edges.     

Contractible edges in minimally k-connected graphs

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 (K₁ + C₄)-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.     

Graphs G for which both G and G¯ are Contraction Critically k-Connected

 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. A k-connected graph with no k-contractible edge is called contraction critically k-connected. For k≥4, we prove that if both G and its complement Gˉ are contraction critically k-connected, then |V(G)|<k ^5/3+4k ^3/2. Received: October, 2001 Final version received: September 18, 2002 AMS Classification: 05C40     

Contractible edges in triangle-free graphs

An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k ²-3k or morek-contractible edges.     

Contractible Cliques in k-Connected Graphs

Kawarabayashi proved that for any integer k≥4, every k-connected graph contains two triangles sharing an edge, or admits a k-contractible edge, or admits a k-contractible triangle. This implies Thomassen's result that every triangle-free k-connected graph contains a k-contractible edge. In this paper, we extend Kawarabayashi's technique and prove a more general result concerning k-contractible cliques. Xingxing Yu was partially supported by NSF grant DMS-0245530 and NSA grant MDA-904-03-1-0052.     

Contractible edges in non-separating cycles

An edge of ak-connected graph is said to bek-contractible if the contraction of the edge results in ak-connected graph. We prove that every triangle-freek-connected graphG has an induced cycleC such that all edges ofC arek-contractible and such thatG–V(C) is (k–3)-connected (k4). This result unifies two theorems by Thomassen [5] and Egawa et. al. [3].Dedicated to Professor Toshiro Tsuzuku on his sixtieth birthday     

Some properties of contraction-critical 5-connected graphs

Let k be a positive integer and let G be a k-connected graph. An edge of G is called k-contractible if its contraction still results in a k-connected graph. A non-complete k-connected graph G is called contraction-critical if G has no k-contractible edge. Let G be a contraction-critical 5-connected graph, Su proved in [J. Su, Vertices of degree 5 in contraction-critical 5-connected graphs, J. Guangxi Normal Univ. 17 (3) (1997) 12-16 (in Chinese)] that each vertex of G is adjacent to at least two vertices of degree 5, and thus G has at least vertices of degree 5. In this paper, we further study the properties of contraction-critical 5-connected graph. In the process, we investigate the structure of the subgraph induced by the vertices of degree 5 of G. As a result, we prove that a contraction-critical 5-connected graph G has at least vertices of degree 5.     

The number of vertices of degree 5 in a contraction-critically 5-connected graph

An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V₅(G) denote the vertex set of a graph G and the set of degree 5 vertices of G, respectively. We prove that each contraction-critically 5-connected graph G has at least |V(G)|/2 vertices of degree 5. We also show that there is a sequence of contraction-critically 5-connected graphs {G_i} such that lim_i→∞|V₅(G_i)|/|V(G_i)|=1/2.     

A constructive characterization of contraction critical 8-connected graphs with minimum degree 9

An edge of a $k$-connected graph is said to be $k$-contractible if its contraction results in a $k$-connected graph. A $k$-connected graph without $k$-contractible edge is said to be contraction critically $k$-connected. Y. Egawa and W. Mader, independently, showed that the minimum degree of a contraction critical $k$-connected graph is at most $\frac{5k}{4}?1$. Hence, the minimum degree of a contraction critical 8-connected graph is either 8 or 9. This paper shows that a graph $G$ is a contraction critical 8-connected graph with minimum degree 9 if and only if $G$ is the strong product of a contraction critical 4-connected graph $H$ and $K_2$.     

收缩临界5-连通图的平均度

M．Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10．本文构造了一个反例证明M．Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界．     

The contractible subgraph of 5-connected graphs

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.     

Local structure of 5- and 6-connected graphs

We prove that if graph on n vertices is minimally and contraction critically 5-connected, then it has 4n/7 vertices of degree 5. We also prove that if graph on n vertices is minimally and contraction critically 6-connected, then it has n/2 vertices of degree 6. Bibliography: 7 titles.     

Covering contractible edges in 3-connected graphs. I: Covers of size three are cutsets

An edge of a 3-connected graph is said to be contractible if its contraction results in a 3-connected graph. In this paper, a covering of contractible edges is studied. We give an alternative proof to the result of Ota and Saito (Scientia (A) 2 (1988) 101–105) that the set of contractible edges in a 3-connected graph cannot be covered by two vertices, and extended this result to a three-vertex covering. We also study the existence of a contractible edge whose contraction preserves a specified cycle, and show that a non-hamiltonian 3-connected graph has a contractible edge whose contraction preserves the circumference.     

Local structure of 7- and 8-connected graphs

We show that if graph on n vertices is minimally and contraction critically k-connected, then it has at least n/2 vertices of degree k for k = 7,8. Bibliography: 17 titles.     

Nonseparating cycles in K-Connected graphs

We show that every k-connected graph with no 3-cycle contains an edge whose contraction results in a k-connected graph and use this to prove that every (k + 3)-connected graph contains a cycle whose deletion results in a k-connected graph. This settles a problem of L. Lovász.     

Paths with restricted degrees of their vertices in planar graphs

In this paper it is proved that every 3-connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23. Analogous results are stated for 3-connected planar graphs of minimum degree 4 and 5. Moreover, for every pair of integers n 3, k 4 there is a 2-connected planar graph such that every path on n vertices in it has a vertex of degree k.     

On the Structure of Contractible Edges in <Emphasis Type="Italic">k</Emphasis>-connected Partial <Emphasis Type="Italic">k</Emphasis>-trees

Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one (k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least |V(G)| + k − 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2k-connected partial 2k-trees.