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.     

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     

A generalization of Dirac’s theorem for K(1,3)-free graphs

It is known that if a 2-connected graphG of sufficiently large ordern satisfies the property that the union of the neighborhoods of each pair of vertices has cardinality at leastn/2, thenG is hamiltonian. In this paper, we obtain a similar generalization of Dirac’s Theorem forK(1,3)-free graphs. In particular, we show that ifG is a 2-connectedK(1,3)-free graph of ordern with the cardinality of the union of the neighborhoods of each pair of vertices at least (n+1)/3, thenG is hamiltonian. We also investigate several other related properties inK(1,3)-free graphs such as traceability, hamiltonian-connectedness, and pancyclicity. Partially Supported by O. N. R. Contract Number N00014-88-K-0070. Partially Supported by O. N. R. Contract Number N00014-85-K-0694.     

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.     

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.     

Bounding the Size of Equimatchable Graphs of Fixed Genus

A graph G is said to be equimatchable if every matching in G extends to (i.e., is a subset of) a maximum matching in G. In an earlier paper with Saito, the authors showed that there are only a finite number of 3-connected equimatchable planar graphs. In the present paper, this result is extended by showing that in a surface of any fixed genus (orientable or non-orientable), there are only a finite number of 3-connected equimatchable graphs having a minimal embedding of representativity at least three. (In fact, if the graphs considered are non-bipartite, the representativity three hypothesis may be dropped.) The proof makes use of the Gallai-Edmonds decomposition theorem for matchings.      

On kernels in perfect graphs

A kernel of a digraphD is a set of vertices which is both independent and absorbant. In 1983, C. Berge and P. Duchet conjectured that an undirected graphG is perfect if and only if the following condition is fulfilled: ifD is an orientation ofG (where pairs of opposite arcs are allowed) and if every clique ofD has a kernel thenD has a kernel. We prove here the conjecture for the complements of strongly perfect graphs and establish that a minimal counterexample to the conjecture is not a complete join of an independent set with another graph.     

The structure of the 4-separations in 4-connected matroids

For a 2-connected matroid M, Cunningham and Edmonds gave a tree decomposition that displays all of its 2-separations. When M is 3-connected, two 3-separations are equivalent if one can be obtained from the other by passing through a sequence of 3-separations each of which is obtained from its predecessor by moving a single element from one side of the 3-separation to the other. Oxley, Semple, and Whittle gave a tree decomposition that displays, up to this equivalence, all non-trivial 3-separations of M. Now let M be 4-connected. In this paper, we define two 4-separations of M to be 2-equivalent if one can be obtained from the other by passing through a sequence of 4-separations each obtained from its predecessor by moving at most two elements from one side of the 4-separation to the other. The main result of the paper proves that M has a tree decomposition that displays, up to 2-equivalence, all non-trivial 4-separations of M.     

Spanning trees with bounded degrees

Lets andk be positive integers. We prove that ifG is ak-connected graph containing no independent set withks+2 vertices thenG has a spanning tree with maximum degree at mosts+1. Moreover ifs3 and the independence number (G) is such that (G)1+k(s–1)+c for some0ck thenG has a spanning tree with no more thanc vertices of degrees+1.     

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 the edge reconstruction of graphs embedded on surfaces

In this paper, we proved that ifG is a 3-connected graph of minimum valency δ = 6χ + 5 with α a non-negative integer and if there exists an embedding ψ ofG on a surface Σ of characteristic ?(Σ) = — α|V(G)∣+ β with the representativity of the embedding ψ ≥ 3, where ψ ε 0,1, thenG is edge reconstructible.     

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.     

Proof of a conjecture of Kahn for non-binary matroids

This note proves a conjecture of Kahn by showing that ifX is a 3-element independent set in a 3-connected non-binary matroid M, thenM has a connected non-binary minor havingX as a basis. This research was partially supported by an LSU Summer Research Grant.     

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     

Embedding (p,p−1) graphs in their complements

A graphG is embeddable in its complement ifG is isomorphic with a subgraph of . A complete characterization is given of those (p,p−1) graphs which are embeddable in their complements. In particular, letG be a (p,p−1) graph wherep≧6 ifp is even andp≧9 ifp is odd; thenG is embeddable in if and only ifG is neither the starK _1,p−1 norK _1,n ∪C ₃ withn≧4.     

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.     

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.     

A new neighborhood union condition for Hamiltonian graphs

For a vertex set {u ₁,u ₂,...,u _k} of a graphG withn vertices, let $$\begin{gathered} s(G;\{ u_1 ,u_2 ,...,u_k \} ) = \sum {1 \leqslant i< j \leqslant k\left| {N(u_i ) \cup N(u_j )} \right|,} \hfill \\ NC_k = \min \{ s(G;\{ x_1 ,...,x_k \} )\} :\{ x_1 ,...,x_k \} is an independent set\} . \hfill \\ \end{gathered} $$ In this paper, we shall prove that ifG is 3-connected andNC ₄≥3n, thenG is either a hamiltonian or Petersen graph. This generalizes some results on the neighborhood union conditions for hamiltonian graphs.     

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.     

The number of contractible edges in 3-connected graphs

An edge of a 3-connected graph is calledcontractible if its contraction results in a 3-connected graph. Ando, Enomoto and Saito proved that every 3-connected graph of order at least five has |G|/2 or more contractible edges. As another lower bound, we prove that every 3-connected graph, except for six graphs, has at least (2|E(G)| + 12)/7 contractible edges. We also determine the extremal graphs. Almost all of these extremal graphsG have more than |G|/2 contractible edges.