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.     

Enumeration of cyclically 4-connected cubic graphs

The number of labeled cyclically 4-connected cubic graphs on n vertices is shown to satisfy a simple recurrence relation. The proof involves the unique decomposition of 3-connected cubic graphs into cyclically 4-connected components.     

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.     

Maximum chromatic polynomials of 2-connected graphs

In this paper we obtain chromatic polynomials P(G; λ) of 2-connected graphs of order n that are maximum for positive integer-valued arguments λ ≧ 3. The extremal graphs are cycles C_n and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{P(G; λ): G is 2-connected of order n and G ≠ C_n} and all extremal graphs relative to this property, with some consequences on the maximum number of 3-colorings in the class of 2-connected graphs of order n having _X(G) = 2 and _X(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2-connected graphs are determined.     

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.     

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.     

Uncontractable 4-connected graphs

The only uncontractable 4-connected graphs are C²_n for n ≥ 5 and the line graphs of the cubic cyclically 4-connected graphs.     

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.     

Decomposition of 3-connected graphs

Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K _3,n for somen3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

Hamiltonian cycles in 3-connected claw-free graphs

In this paper, we show that every 3-connected claw-free graph on n vertices with δ ≥ (n + 5)/5 is hamiltonian. © 1993 John Wiley & Sons, Inc.     

Characterization of maximum critically 2-connected graphs

A graph G is critically 2-connected if G is 2-connected but, for any point p of G, G — p is not 2-connected. Critically 2-connected graphs on n points that have the maximum number of lines are characterized and shown to be unique for n ? 3, n ≠ 11.     

Hamiltonicity of 4-connected graphs

Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.     

Removable edges in 3-connected graphs

An edge e of a 3-connected graph G is said to be removable if G - e is a subdivision of a 3-connected graph. If e is not removable, then e is said to be nonremovable. In this paper, we study the distribution of removable edges in 3-connected graphs and prove that a 3-connected graph of order n ≥ 5 has at most [(4 n — 5)/3] nonremovable edges.     

Connected,locally 2-connected,K1,3-free graphs are panconnected

A graph G is locally n-connected, n ≥ 1, if the subgraph induced by the neighborhood of each vertex is n-connected. We prove that every connected, locally 2-connected graph containing no induced subgraph isomorphic to K_1,3 is panconnected.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

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 K₆. 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 K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

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.     

On k -diameter of k -connected graphs

Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d _k (G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d _k (G). For a fixed positive integer d, some conditions to insure d _k (G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d _k (G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. Supported by NNSF of China (19971086).     

Hamiltonian graphs involving distances

Let G be a graph of order n. We show that if G is a 2-connected graph and max{d(u), d(v)} + |N(u) U N(v)| ≥ n for each pair of vertices u, v at distance two, then either G is hamiltonian or G ?3K_n/3 U T₁ U T₂, where n ? O (mod 3), and T₁ and T₂ are the edge sets of two vertex disjoint triangles containing exactly one vertex from each K_n/3. This result generalizes both Fan's and Lindquester's results as well as several others.     

Circumferences and minimum degrees in 3-connected claw-free graphs

In this paper, we prove that every 3-connected claw-free graph G on n vertices contains a cycle of length at least min{n,6δ−15}, thereby generalizing several known results.     

Generating planar 4-connected graphs

In this paper, we introduce three operations on planar graphs that we call face splitting, double face splitting, and subdivision of hexagons. We show that the duals of the planar 4-connected graphs can be generated from the graph of the cube by these three operations. That is, given any graphG that is the dual of a planar 4-connected graph, there is a sequence of duals of planar 4-connected graphsG ₀,G ₁, …,G _n such thatG ₀ is the graph of the cube,G _n=G, and each graph is obtained from its predecessor by one of our three operations. Research supported by a Sloan Foundation fellowship and by NSF Grant#GP-27963.