Removable edges in cycles of a <Emphasis Type="Italic">k</Emphasis>-connected graph

An edge e of a k-connected graph G is said to be a removable edge if G ⊖ e is still k-connected, where G ⊖ e denotes the graph obtained from G by deleting e to get G − e, and for any end vertex of e with degree k − 1 in G − e, say x, delete x, and then add edges between any pair of non-adjacent vertices in N _G−e (x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4).     

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.     

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.     

Removable Edges in Longest Cycles of 4-Connected Graphs

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     

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 of cycles in 5-connected graphs

Let G be a 5-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 each vertex x of degree 4 in G?e, delete x from G?e and then completely connect the 4 neighbors of x by K ₄. If multiple edges occur, we use single edge to replace them. The final resultant graph is denoted by G ? e. If G ? e is still 5-connected, then e is called a removable edge of G. In this paper, we investigate the distribution of removable edges in a cycle of a 5-connected graph. And we give examples to show some of our results are best possible in some sense.     

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.     

Generating thec *5-connected graphs

A planar 3-valent 3-connected graph is said to becyclically n-connected provided it is possible to separate two circuits by cutting edges, and at leastn edges must be cut to do so. The graph is said to bestrongly cyclically n-connected provided it is cyclicallyn-connected and any separation of two circuits by cutting edges leaves one component consisting of just a simple circuit. We give a method of generating all strongly cyclically 5-connected graphs by certain types of facet splitting.     

Removable edges in cyclically 4-edge-connected cubic graphs

We consider various ways of obtaining smaller cyclically 4-edge-connected cubic graphs from a given such graph. In particular, we consider removable edges: an edgee of a cyclically 4-edge-connected cubic graphG is said to be removable ifG is also cyclically 4-edge-connected, whereG is the cubic graph obtained fromG by deletinge and suppressing the two vertices of degree 2 created by the deletion. We prove that any cyclically 4-edge-connected cubic graphG with at least 12 vertices has at least 1/5(|E(G)| + 12) removable edges, and we characterize the graphs with exactly 1/5(|E(G)| + 12) removable edges.This work was carried out while the first author held a Niels Bohr Fellowship from the Royal Danish Academy of Sciences.     

The 3-Connected Graphs with Exactly k Non-Essential Edges

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.     

An Extremal Problem on Contractible Edges in 3-Connected Graphs

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The existence of contractible edges is a very useful induction tool. Let G be a simple 3-connected graph with at least five vertices. Wu [7] proved that G has at most vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly vertices that are not incident to contractible edges. We show that all such graphs can be constructed from either a single vertex or a 3-edge-connected graph (multiple edges are allowed, but loops are not allowed) by a simple graph operation. Research partially supported by an ONR grant under grant number N00014-01-1-0917     

On Non-Essential Edges in 3-Connected Graphs

 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     

Contractible edges inn-connected graphs with minimum degree greater than or equal to [5n/4]

It is proved that ifG is ann-connected graph with minimum degree greater than or equal to [5n/4],n 4, thenG has an edgee such that the graph obtained fromG by contractinge is stilln-connected.Dedicated to Professor Nagayoshi Iwahori on his 60th birthday     

The 3-Connected Graphs with Exactly Three Non-Essential Edges

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     

5连通图中的可去边

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least （3│G│ ＋ 2）/2 removable edges.     

3连通平面图的可去边数

设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。     

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.     

Long cycles and spanning subgraphs of locally maximal 1-planar graphs

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is Hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many nontraceable 5-connected 1-planar graphs are presented.     

Non-contractible edges in a 3-connected graph

An edgee in a 3-connected graphG is contractible if the contraction ofe inG results in a 3-connected graph; otherwisee is non-contractible. In this paper, we prove that the number of non-contractible edges in a 3-connected graph of orderp≥5 is at most $$3p - \left[ {\frac{3}{2}(\sqrt {24p + 25} - 5} \right],$$ and show that this upper bound is the best possible for infinitely many values ofp.     

On fixing edges in graph minors

An area of much recent research activity has been involved with tying the presence of certain minors in a matroid to specific elements of this matroid. The aim of this paper is to show that there are exactly two 3-connected simple graphsG with at least four edges and the property that ifH is a 3-connected simple graph havingG as a minor ande andf are edges ofH, thenH has a minor isomorphic toG which containse andf in its edge set. Some extensions of this result are also considered.