2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003     

Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9

A graph H is light in a given class of graphs if there is a constant w such that every graph of the class which has a subgraph isomorphic to H also has a subgraph isomorphic to H whose sum of degrees in G is ≤ w. Let be the class of simple planar graphs of minimum degree ≥ 4 in which no two vertices of degree 4 are adjacent. We denote the minimum such w by w(H). It is proved that the cycle C_s is light if and only if 3 ≤ s ≤ 6, where w(C₃) = 21 and w(C₄) ≤ 35. The 4‐cycle with one diagonal is not light in , but it is light in the subclass consisting of all triangulations. The star K_1,s is light if and only if s ≤ 4. In particular, w(K_1,3) = 23. The paths P_s are light for 1 ≤ s ≤ 6, and heavy for s ≥ 8. Moreover, w(P₃) = 17 and w(P₄) = 23. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 261–295, 2003     

Characterizing 3‐connected planar graphs and graphic matroids

A well‐known result of Tutte states that a 3‐connected graph G is planar if and only if every edge of G is contained in exactly two induced non‐separating circuits. Bixby and Cunningham generalized Tutte's result to binary matroids. We generalize both of these results and give new characterizations of both 3‐connected planar graphs and 3‐connected graphic matroids. Our main result determines when a natural necessary condition for a binary matroid to be graphic is also sufficient. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 165–174, 2010     

One‐way infinite 2‐walks in planar graphs

We prove that every 3‐connected 2‐indivisible infinite planar graph has a 1‐way infinite 2‐walk. (A graph is 2‐indivisible if deleting finitely many vertices leaves at most one infinite component, and a 2‐walk is a spanning walk using every vertex at most twice.) This improves a result of Timar, which assumed local finiteness. Our proofs use Tutte subgraphs, and allow us to also provide other results when the graph is bipartite or an infinite analog of a triangulation: then the prism over the graph has a spanning 1‐way infinite path.     

Contractible subgraphs in k‐connected graphs

For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007     

Spanning even subgraphs of 3‐edge‐connected graphs

By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connectivity, we can find a spanning even subgraph in which every component has at least five vertices. We show that this is in some sense best possible by constructing an infinite family of 3‐edge‐connected graphs in which every spanning even subgraph has a 5‐cycle as a component. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 37–47, 2009     

Long cycles in 3‐connected graphs in orientable surfaces

In this article, we apply a cutting theorem of Thomassen to show that there is a function f: N → N such that if G is a 3‐connected graph on n vertices which can be embedded in the orientable surface of genus g with face‐width at least f(g), then G contains a cycle of length at least cn, where c is a constant not dependent on g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 69–84, 2002     

Maximum bipartite subgraphs of cubic triangle-free planar graphs

Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to .     

Codiameters of 3‐connected 3‐domination critical graphs

A graph G is 3‐domination critical if its domination number γ is 3 and the addition of any edge decreases γ by 1. Let G be a 3‐connected 3‐domination critical graph of order n. In this paper, we show that there is a path of length at least n?2 between any two distinct vertices in G and the lower bound is sharp. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 76–85, 2002     

Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

Relative length of longest paths and cycles in 3‐connected graphs

For a graph G, let p(G) denote the order of a longest path in G and c(G) the order of a longest cycle in G, respectively. We show that if G is a 3‐connected graph of order n such that for every independent set {x₁, x₂, x₃, x₄}, then G satisfies c(G) ≥ p(G) ? 1. Using this result, we give several lower bounds to the circumference of a 3‐connected graph. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 137–156, 2001     

A degree sum condition for longest cycles in 3‐connected graphs

For a graph G, we denote by d_G(x) and κ(G) the degree of a vertex x in G and the connectivity of G, respectively. In this article, we show that if G is a 3‐connected graph of order n such that d_G(x) + d_G(y) + d_G(z) ≥ d for every independent set {x, y, z}, then G contains a cycle of length at least min{d ? κ(G), n}. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 277–283, 2007     

Large ‐ or ‐Minors in 3‐Connected Graphs

There are numerous results bounding the circumference of certain 3‐connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3‐connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer such that every 3‐connected graph with at least n vertices contains a ‐ or ‐minor. This result implies that the size of the largest bond in a 3‐connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3‐connected graph by showing that any 3‐connected graph on n vertices has a bond of size at least . In addition, we show the following: Let G be a 3‐connected planar or cubic graph on n vertices. Then for any , G has a ‐minor with , and thus a bond of size at least .     

Minors in large almost‐5‐connected non‐planar graphs

It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐separations contain a “small” side. As a corollary, every sufficiently large almost‐5‐connected non‐planar graph contains both a K_{3, 4}‐minor and a ‐minor. The connectivity condition cannot be reduced to 4‐connectivity, as there are known infinite families of 4‐connected non‐planar graphs that do not contain a K_{3, 4}‐minor. Similarly, there are known infinite families of 4‐connected non‐planar graphs that do not contain a ‐minor.     

Long cycles passing through vertices in k‐connected graphs

In this article, we consider the following problem proposed by Locke and Zhang in 1991: Let G be a k‐connected graph with minimum degree d and X a set of m vertices on a cycle of G. For which values of m and k, with , must G have a cycle of length at least passing through X? Fujisawa and Yamashita solved this problem for the case and in 2008. We provide an affirmative answer to this problem for the case of and .     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs

In this paper, we show that if G is a 3‐edge‐connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003     

Counting 5‐connected planar triangulations

Let t_n be the number of rooted 5‐connected planar triangulations with 2n faces. We find t_n exactly for small n, as well as an asymptotic formula for n → ∞. Our results are found by compositions of lower connectivity maps whose faces are triangles or quadrangles. We also find the asymptotic number of cyclically 5‐edge connected cubic planar graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 18–35, 2001