On well-covered triangulations: Part II

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part I, Discrete Appl. Math., 132, 2004, 97-108] that there are no 5-connected planar well-covered triangulations. It is the aim of the present paper to completely determine the 4-connected well-covered triangulations containing two adjacent vertices of degree 4. In a subsequent paper [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part III (submitted for publication)], we show that every 4-connected well-covered triangulation contains two adjacent vertices of degree 4 and hence complete the task of characterizing all 4-connected well-covered planar triangulations. There turn out to be only four such graphs. This stands in stark contrast to the fact that there are infinitely many 3-connected well-covered planar triangulations.     

On well-covered triangulations: Part III

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper Finbow et al. (2004) [3] that there are no 5-connected planar well-covered triangulations, and in Finbow et al. (submitted for publication) [4] that there are exactly four 4-connected well-covered triangulations containing two adjacent vertices of degree 4. It is the aim of the present paper to complete the characterization of 4-connected well-covered triangulations by showing that each such graph contains two adjacent vertices of degree 4.     

On the toughness index of planar graphs

The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph.     

Cycle Covers of Planar 2-Edge-Connected Graphs

A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained.     

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.      

Generating planar 4-connected graphs

In this paper, we introduce three operations on planar graphs that we call face splitting, double face splitting, and subdivision of hexagons. We show that the duals of the planar 4-connected graphs can be generated from the graph of the cube by these three operations. That is, given any graphG that is the dual of a planar 4-connected graph, there is a sequence of duals of planar 4-connected graphsG ₀,G ₁, …,G _n such thatG ₀ is the graph of the cube,G _n=G, and each graph is obtained from its predecessor by one of our three operations. Research supported by a Sloan Foundation fellowship and by NSF Grant#GP-27963.     

The chromatic connectivity of graphs

A graphG ischromatically k-connected if every vertex cutset induces a subgraph with chromatic number at leastk. This concept arose in some work, involving the third author, on Ramsey Theory. (For the reference, see the text.) Here we begin the study of chromatic connectivity for its own sake. We show thatG is chromaticallyk-connected iff every homomorphic image of it isk-connected. IfG has no triangles then it is at most chromatically 1-connected, but we prove that the Kneser graphs provide examples ofK ₄-free graphs with arbitrarily large chromatic connectivity. We also verify thatK ₄-free planar graphs are at most chromatically 2-connected.This work was supported by grants from NSERC of Canada.     

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.     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

Hamiltonian properties of polyhedra with few 3-cuts—A survey

We give an overview of the most important techniques and results concerning the hamiltonian properties of planar 3-connected graphs with few 3-vertex-cuts. In this context, we also discuss planar triangulations and their decomposition trees. We observe an astonishing similarity between the hamiltonian behavior of planar triangulations and planar 3-connected graphs. In addition to surveying, (i) we give a unified approach to constructing non-traceable, non-hamiltonian, and non-hamiltonian-connected triangulations, and show that planar 3-connected graphs (ii) with at most one 3-vertex-cut are hamiltonian-connected, and (iii) with at most two 3-vertex-cuts are 1-hamiltonian, filling two gaps in the literature. Finally, we discuss open problems and conjectures.     

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.     

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     

Small cycle double covers of 4-connected planar graphs

Acycle double cover of a graph,G, is a collection of cycles,C, such that every edge ofG lies in precisely two cycles ofC. TheSmall Cycle Double Cover Conjecture, proposed by J. A. Bondy, asserts that every simple bridgeless graph onn vertices has a cycle double cover with at mostn–1 cycles, and is a strengthening of the well-knownCycle Double Cover Conjecture. In this paper, we prove Bondy's conjecture for 4-connected planar graphs.     

On the number of Hamiltonian cycles in triangulations

It is proved that if a planar triangulation different from K₃ and K₄ contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [2], this yields that, for n ? 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar triangulation on n vertices is four. We also show that this theorem holds for triangulations of arbitrary surfaces and for 3-connected triangulated graphs.     

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

A t-spanner of an undirected, unweighted graph G is a spanning subgraph of G with the added property that for every pair of vertices in G, the distance between them in is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t2. For t5, the problem remains NP-hard for planar graphs, whereas for t{2,3,4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation.     

Removable edges in 3-connected graphs

An edge e of a 3-connected graph G is said to be removable if G - e is a subdivision of a 3-connected graph. If e is not removable, then e is said to be nonremovable. In this paper, we study the distribution of removable edges in 3-connected graphs and prove that a 3-connected graph of order n ≥ 5 has at most [(4 n — 5)/3] nonremovable edges.     

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.     

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.     

On Hamilton cycles in certain planar graphs

Let G be a 2-connected plane graph with outer cycle X_G such that for every minimal vertex cut S of G with |S| ≤ 3, every component of G\S contains a vertex of X_G. A sufficient condition for G to be Hamiltonian is presented. This theorem generalizes both Tutte's theorem that every 4-connected planar graph is Hamiltonian, as well as a recent theorem of Dillencourt about NST-triangulations. A linear algorithm to find a Hamilton cycle can be extracted from the proof. One corollary is that a 4-connected planar graph with the vertices of a triangle deleted is Hamiltonian. © 1996 John Wiley & Sons, Inc.     

Paths with restricted degrees of their vertices in planar graphs

In this paper it is proved that every 3-connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23. Analogous results are stated for 3-connected planar graphs of minimum degree 4 and 5. Moreover, for every pair of integers n 3, k 4 there is a 2-connected planar graph such that every path on n vertices in it has a vertex of degree k.