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.     

Removable Edges and Chords of Longest Cycles in 3-Connected Graphs

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.     

Biased Expansions of Biased Graphs and Their Chromatic Polynomials

A biased graph is a graph with a distinguished set of circles, such that if two circles in the set are contained in a theta graph, then so is the third circle of the theta graph. We introduce a new biased graph, a biased expansion of a biased graph, that satisfies certain lifting and projection properties with the original biased graph. We relate the chromatic polynomials of a biased graph and its biased expansions, thus generalizing a biased-graph result of Zaslavsky [7] and a hyperplane result of Ehrenborg and Readdy [1]. We also determine which biased expansions have supersolvable bias matroids.     

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.     

Large non-planar graphs and an application to crossing-critical graphs

We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K4,k, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices.     

Diamond-free circle graphs are Helly circle

The diamond is the graph obtained from K₄ by deleting an edge. Circle graphs are the intersection graphs of chords in a circle. Such a circle model has the Helly property if every three pairwise intersecting chords intersect in a single point, and a graph is Helly circle if it has a circle model with the Helly property. We show that the Helly circle graphs are the diamond-free circle graphs, as conjectured by Durán. This characterization gives an efficient recognition algorithm for Helly circle graphs.     

On the Structure of Contractible Vertex Pairs in Chordal Graphs

An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph.     

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.     

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

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.     

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.     

Hamiltonian connectedness in 3-connected line graphs

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 K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) 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.     

Contractible Edges in 7-Connected Graphs

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)     

On Group Connectivity of Graphs

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z ₃-flow and Jaeger et al. [Group connectivity of graphs–a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B 56 (1992) 165-182] further conjectured that every 5-edge-connected graph is Z ₃-connected. These two conjectures are in general open and few results are known so far. A weaker version of Tutte’s conjecture states that every 4-edge-connected graph with each edge contained in a circuit of length at most 3 admits a nowhere-zero Z ₃-flow. Devos proposed a stronger version problem by asking if every such graph is Z ₃-connected. In this paper, we first answer this later question in negative and get an infinite family of such graphs which are not Z ₃-connected. Moreover, motivated by these graphs, we prove that every 6-edge-connected graph whose edge set is an edge disjoint union of circuits of length at most 3 is Z ₃-connected. It is a partial result to Jaeger’s Z ₃-connectivity conjecture. Received: May 23, 2006. Final version received: January 13, 2008     

Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs

Given a vertex r of a 3-connected graph G, we show how to find three independent spanning trees of G rooted at r. Our proof is based on showing that every 3-connected graph has a nonseparating ear decomposition. This extends Whitney's characterisation that a graph is 2-connected iff it has an ear decomposition. We also show that a nonseparating ear decomposition can be constructed in O(VE) time, and hence, three independent spanning trees can be found in O(VE) time. We construct a nonseparating ear decomposition by solving the following problem at most V times. Given an edge tr and a vertex u of a 3-connected graph G, find a nonseparating induced cycle of G through tr and avoiding u. W. T. Tutte (Proc. London Math. Soc. 13 (1963), 743–767) first showed that such a cycle can always be found. We give a linear time algorithm for this.     

Hamiltonian Connectedness in Claw-Free Graphs

If every vertex cut of a graph G contains a locally 2-connected vertex, then G is quasilocally 2-connected. In this paper, we prove that every connected quasilocally 2-connected claw-free graph is Hamilton-connected.     

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.     

Nonseparating Induced Cycles Consisting of Contractible Edges in k-Connected Graphs

It is proved that if G is a k-connected graph which does not contain K₄⁻, 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.     

On the 1-factors of n-connected graphs

L. W. Beineke and M. D. Plummer have recently proved [1] that every n-connected graph with a 1-factor has at least n different 1-factors. The main purpose of this paper is to prove that every n-connected graph with a 1-factor has at least as many as n(n − 2)(n − 4) … 4 · 2, (or: n(n − 2)(n − 4) … 5 · 3) 1-factors. The main lemma used is: if a 2-connected graph G has a 1-factor, then G contains a vertex V (and even two such vertices), such that each edge of G, incident to V, belongs to some 1-factor of G.     

Connectivity of iterated line graphs

Let k≥0 be an integer and L^k(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L²(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 κ(L²(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs.