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.     

Enumerative Properties of Rooted Circuit Maps

In 1966, Barnette introduced a set of graphs, called circuit graphs, which are obtained from 3-connected planar graphs by deleting a vertex. Circuit graphs and 3-connected planar graphs share many interesting properties which are not satisfied by general 2-connected planar graphs. Circuit graphs have nice closure properties which make them easier to deal with than 3-connected planar graphs for studying some graph-theoretic properties. In this paper, we study some enumerative properties of circuit graphs. For enumeration purpose, we define rooted circuit maps and compare the number of rooted circuit maps with those of rooted 2-connected planar maps and rooted 3-connected planar maps.     

On the sum of all distances in chromatic blocks

In this paper all 2-connected k-chromatic graphs of order n with the maximum sum of all distances between their vertices are characterized for every k ≥ 2, thus strengthening a result of J. Plesnik. Moreover, several auxiliary results are proved on chromatic critical graphs and 2-connected graphs.     

具有割点的标号Euler图的计数

本文讲座了具有k(k≥2）个割点,并且所有割点均分布在一个2－连能Euler图的标号Euler图的计数,在这里给出了有含有n个2－连能Euler图和k(k≥2）个割点,并且所有割点均分布在其中一2－连能Euler图的标号Euler图的指数型生成函数。     

On the minimum number of edges of two-connected graphs with given diameter

We answer the following question: what is the minimum number of edges of a 2-connected graph with a given diameter? This problem stems from survivable telecommunication network design with grade-of-service constraints. In this paper, we prove tight bounds for 2-connected graphs and for 2-edge-connected graphs. The bound for 2-connected graphs was a conjecture of B. Bollobás (AMH 75–80) [3].     

K1,4-自由的模κ泛圈图

设G是2-连通的K1，4自由图．本文证明了当δ(G)≥κ 1时，G是模κ泛圈图．这一结果肯定了猜想2，继而也肯定了Thomassen猜想在2-连通图中的正确性．     

Smallest claw-free, 2-connected,nontraceable graphs and the construction of maximal nontraceable graphs

We determine the smallest claw-free, 2-connected, nontraceable graphs and use one of these graphs to construct a new family of 2-connected, claw-free, maximal nontraceable graphs.     

Decomposition of perfect graphs

We describe composition and decomposition schemes for perfect graphs, which generalize all recent results in this area, e.g., the amalgam and the 2-amalgam split. Our approach is based on the consideration of induced cycles and their complements in perfect graphs (as opposed to the consideration of cycles for defining biconnected or 3-connected graphs). Our notion of 1-inseparable graphs is “parallel” to that of biconnected graphs in that different edges in different inseparable components of a graph are not contained in any induced cycle or any complement of an induced cycle. Furthermore, in a special case which generalizes the join operation, this definition is self-complementary in a natural fashion. Our 2-composition operation, which only creates even induced cycles in the composed graphs, is based on two perfection-preserving vertex merge operations on perfect graphs. As a by-product, some new properties of minimally imperfect graphs are presented.     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

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.     

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.     

Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs

Summary A variety of examples of 4-connected 4-regular graphs with no pair of disjoint Hamiltonian circuits were constructed in response to Nash-Williams conjecture that every 4-connected 4-regular graph is Hamiltonian and also admits a pair of edge-disjoint Hamiltonian circuits. Nash-Williams's problem is especially interesting for planar graphs since 4-connected planar graphs are Hamiltonian. Examples of 4-connected 4-regular planar graphs in which every pair of Hamiltonian circuits have edges in common are included in the above mentioned examples.B. Grünbaum asked whether 5-connected planar graphs always admit a pair of disjoint Hamiltonian circuits. In this paper we introduce a technique that enables us to construct infinitely many examples of 5-connected planar graphs, 5-regular and non regular, in which every pair of Hamiltonian circuits have edges in common.     

A classification of 4-connected graphs

Having observed Tutte's classification of 3-connected graphs as those attainable from wheels by line addition and point splitting and Hedetniemi's classification of 2-connected graphs as those obtainable from K₂ by line addition, subdivision and point addition, one hopes to find operations which classify n-connected graphs as those obtainable from, for example, K_n+1. In this paper I give several generalizations of the above operations and use Halin's theorem to obtain two variations of Tutte's theorem as well as a classification of 4-connected graphs.     

Connectivity in bicircular matroids

Tutte has defined n-connection for matroids and proved a connected graph is n-connected if and only if its polygon matroid is n-connected. In this paper we introduce a new notion of connection in graphs, called n-biconnection, and prove an analogous theorem for graphs and their bicircular matroids. Results concerning 3-biconnected graphs are also presented.     

On 4-connected 4-regular graphs without even cycle decompositions

An even cycle decomposition of a graph is a partition of its edges into even cycles. Markström constructed infinitely many 2-connected 4-regular graphs without even cycle decompositions. Má?ajová and Mazák then constructed an infinite family of 3-connected 4-regular graphs without even cycle decompositions. In this note, we further show that there exists an infinite family of 4-connected 4-regular graphs without even cycle decompositions.     

Lower Bounds for Locally Highly Connected Graphs

We propose a conjecture regarding the lower bound for the number of edges in locally k-connected graphs and we prove it for \(k=2\). In particular, we show that every connected locally 2-connected graph is \(M_3\)-rigid. For the special case of surface triangulations, this fact was known before using topological methods. We generalize this result to all locally 2-connected graphs and give a purely combinatorial proof. Our motivation to study locally k-connected graphs comes from lower bound conjectures for flag triangulations of manifolds, and we discuss some more specific problems in this direction.     

Traceability in Small Claw-Free Graphs

We prove that a claw-free, 2-connected graph with fewer than 18 vertices is traceable, and we determine all non-traceable, claw-free, 2-connected graphs with exactly 18 vertices and a minimal number of edges. This complements a result of Matthews on Hamiltonian graphs.     

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.     

Hamilton cycles in 6-connected claw-free graphs (Extended abstract)

Thomassen conjectured in 1986 that every 4-connected line graph is hamiltonian. In this paper, we show that 6-connected line graphs are hamiltonian, improving on an analogous result for 7-connected line graphs due to Zhan in 1991. Our result implies that every 6-connected claw-free graph is hamiltonian.     

Minimally 2-edge connected graphs

A constructive characterization of minimally 2-edge connected graphs, similar to those of Dirac for minimally 2-connected graphs is given.