Shortness parameters of families of regular planar graphs with two or three types of face

This paper is concerned with non-Hamiltonian planar graphs. It is shown that the class of 3-connected cubic planar graphs whose faces are all pentagons or 10-gons contains non-Hamiltonian members and that the shortness coefficient of this class of graphs is less than unity. For several classes of 3-connected regular planar graphs, of valency 4 or 5, it is shown that the shortness exponent is less than unity.     

Shortness parameters for planar graphs with faces of only one type

We construct infinite sequences of non-Hamiltonian graphs and use them to show that the shortness exponent (or, in some cases, the shortness coefficient) is less than one for many classes of 3-connected planar graphs whose faces are all r-gons and whose vertices are all p-valent or q-valent, where p < q. Three of the five possible values of (r, p) are considered, namely (4.3). (3,3), and (3,4), in conjunction with most of the possible corresponding values of q.     

Non-Hamiltonian non-Grinbergian graphs

Settling a question of Tutte and a similar question of Grünbaum and Zaks, we present a 3-valent 3-connected planar graph that has only pentagons and octagons, has 92 (200, respectively) vertices and its longest circuit (path, respectively) contains at most 90 (198, respectively) vertices; moreover, it is shown that the family of all 3-valent 3-connected planar graphs, having n-gons only if n≡ 2 (mod3) (or n≡ 1 (mod3)), has a shortness exponent which is less than one.     

On regular graphs and Hamiltonian circuits,including answers to some questions of Joseph Zaks

A graph is called l-ply Hamiltonian if it admits l edge-disjoint Hamiltonian circuits. The following results are obtained: (1) When n ≥ 3 and 0 ≤ 2l ≤ n there exists an n-connected n-regular graph that is exactly l-ply Hamiltonian. (2) There exist 5-connected 5-regular planar graphs that are not doubly (i.e. 2-ply) Hamiltonian, one with only 132 vertices and another with only three types of face, namely 3-, 4- and 12-gons. (3) There exist 3-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 76 vertices and another that has no Hamiltonian paths and has only 128 vertices. (4) There exist 5-edge-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 176 vertices and another that has no Hamiltonian paths and has only 512 vertices. Result (1) was known in the special cases $\text{l = [}\text{n}\text{2}\text{]}$ (an old result) and l = 0 (due to G. H. J. Meredith, 1973). The special case l = 1 provides a negative answer to question 4 in a recent paper by Joseph Zaks and implies Corollary 1 to Zaks' Theorem 1. Results (2) and (3) involve graphs with considerably fewer vertices (and, in one case, fewer types of face) than Zaks' corresponding graphs and provide partial answers to his questions 1 and 3. Result (4) involves graphs that satisfy a stronger condition than those of Zaks but still have fewer vertices.     

Hamiltonian pancyclic graphs

The class of 3-connected bipartite cubic graphs is shown to contain a non-Hamiltonian graph with only 78 vertices and to have a shortness exponent less than one.     

Pairs of Hamiltonian circuits in 5-connected planar graphs

Settling a problem raised by B. Grünbaum, J. Malkevitch, and the author, we present 5-valent 5-connected planar graphs that admit no pairs of edgedisjoint Hamiltonian circuits; our smallest example has 176 vertices. This is used to construct an infinite family of 5-valent 5-connected planar graphs, in which every member has the property that any pair of Hamiltonian circuits in it share at least about $\text{1}\text{168}$ of their edges. We construct 4- and 5-valent, 3-connected non-Hamiltonian planar graphs.     

A shortness exponent for r-regular r-connected graphs

Let r≧ 3 be an integer. It is shown that there exists ε= ε(r), 0 < ε < 1, and an integer N = N(r) > 0 such that for all n ≧ N (if r is even) or for all even n ≧ N(if r is odd), there is an r-connected regular graph of valency r on exactly n vertices whose longest cycles have fewer than n^ε vertices.     

Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003     

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.     

Embeddings of chemical graphs in hypercubes

We study planar graphs embedded in the plane that have chemical applications: the degrees of all vertices are 3 or 2, all internal faces but one or two arer-gons, and each internal face is a simply connected domain. For wide classes of such graphs, we solve the existence problem for embeddings of the graph metric on the vertices in multidimensional cubes or cubical lattices preserving or doubling all the distances. Incidentally we present a complete classification of some interesting families of such graphs. Translated fromMatematicheskie Zametki, Vol. 68, No. 3, pp. 339–352, September, 2000.     

Longest cycles in polyhedral graphs

A sequence of polyhedral graphsG _n is constructed, having only 3-valent and 8-valent vertices and having only 3-gons and 8-gons as faces with the property that the shortness exponent of the sequence as well as the shortness exponent of the sequence of duals is smaller than one.     

Computational Complexity of the Vertex Cover Problem in the Class of Planar Triangulations

We study the computational complexity of the vertex cover problem in the class of planar graphs (planar triangulations) admitting a plane representation whose faces are triangles. It is shown that the problem is strongly NP-hard in the class of 4-connected planar triangulations in which the degrees of vertices are of order O(log n), where n is the number of vertices, and in the class of plane 4-connected Delaunay triangulations based on the Minkowski triangular distance. A pair of vertices in such a triangulation is adjacent if and only if there is an equilateral triangle ?(p, λ) with p ∈ R² and λ > 0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ?(p, λ) = p + λ? = {x ∈ R²: x = p + λa, a ∈ ?}; here ? is the equilateral triangle with unit sides such that its barycenter is the origin and one of the vertices belongs to the negative y-axis. Keywords: computational complexity, Delaunay triangulation, Delaunay TD-triangulation.     

4-valent graphs

Let {p_k}k≥2, k≠4 be a sequence of non-negative integers which satisfies 8 + Σ_k≥3(k — 4)p_k = 0. Then there exists an integer p₄ such that there exists a 2-connected planar graph with exactly p_k k-gons as faces for all k ≥ 2. This paper determines all such p₄ when p_k = 0 for k ≥ 5 and determines that there is a constant C ≥ 1 such that for some m ≤ p₂ + 1/4p₃ + C, there exists a 2-connected planar graph with exactly p_k faces for each p₄ = m + 2w, w a positive integer. When there exists at least one odd k ≥ 3 for which p_k ≠ 0, the coefficient 2 of w in the above equation may be replaced by 1. These conclusions do not hold if the coefficients of p₂ and p₃ are any smaller than 1 and 1/4, respectively.     

Longest cycles in r-regular r-connected graphs

Let r ≥ 3 be an integer, and ε > 0 a real number. It is shown that there is an integer N(r, ε) such that for all n ≥ N (if r is even) or for all even n ≥ N (if r is odd), there is an r-connected regular graph of valency r on exactly n vertices whose longest cycles have fewer than εn vertices. That is, the number ε > 0, no matter how small, is a “shortness coefficient” for the family of r-valent regular r-connected graphs.     

Contractible Non-Edges in Triangle-Free Graphs

Thomassen has proved that every triangle-free k-connected graph contains a pair of adjacent vertices whose identification yields again a k-connected graph. We study the existence of a pair of nonadjacent vertices whose identification preserves k-connectivity. In particular, we present a reduction theorem for the class of all bipartite, k-connected graphs. Revised: January 7, 1999     

A Note on the Shortness Coefficient and the Hamiltonicity of 4-Connected Line Graphs

Thomassen proposed a well-known conjecture: every 4-connected line graph is hamiltonian. In this note, we show that Thomassens conjecture is equivalent to the statement that the shortness coefficient of the class of all 4-connected line graphs is one and the statement that the shortness coefficient of the class of all 4-connected claw-free graphs is one respectively.Research partially supported by the fund of the basic research of Beijing Institute of Technology, by the fund of Natural Science of Jiangxi Province and by grant No. LN00A056 of the Czech Ministry of Education     

Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes

We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f–1)×(f–1) grid. Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3.The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof.     

Filling of a given boundary by p-gons and related problems

We consider here (p,s)-polycycles (3ps) i.e. plane graphs, such that all interior faces are p-gons, all interior vertices are s-valent and any vertex of the boundary (i.e. the exterior face) has valency within [2,s]. The boundary sequence of a (p,s)-polycycle P is the sequence b(P) enumerating, up to a cyclic shift or reversal, the consecutive valencies of vertices of the boundary. We show that the values p=3,4 are the only ones, such that the boundary sequence defines its (p,3)-filling (i.e. a (p,3)-polycycle with given boundary) uniquely.Also we give new results in the enumeration of maps M_n(p,q) (i.e. plane 3-valent maps with only p- and q-gonal faces, such that the q-gons are organized in an n-ring) and two of their generalizations.Both problems are similar (3-valent filling by p-gons of a boundary or of a ring of q-gons) and the same programs were used for both computations.     

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.     

Covalence sequences of planar vertex-homogeneous maps

Given a cyclic d-tuple of integers at least 3, we consider the class of all 1-ended 3-connected d-valent planar maps such that every vertex manifests this d-tuple as the (clockwise or counterclockwise) cyclic order of covalences of its incident faces. We obtain necessary and/or sufficient conditions for the class to contain a Cayley map, a non-Cayley map whose underlying graph is a Cayley graph, a vertex-transitive graph whose subgroup of orientation-preserving automorphisms acts (or fails to act) vertex-transitively, a non-vertex-transitive map, or no planar map at all.