An upper bound on the length of a Hamiltonian walk of a maximal planar graph

A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p - 3)/2.     

Every connected,locally connected nontrivial graph with no induced claw is hamiltonian

A graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on p ≥ 3 vertices and having no induced K_1,3 is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtained as corollaries.     

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.     

On certain Hamiltonian cycles in planar graphs

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least distinct Hamiltonian cycles. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 81–96, 1999     

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.     

Untangling Polygons and Graphs

Untangling is a process in which some vertices in a drawing of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C _n while keeping Ω(n ^2/3) vertices fixed. For any connected graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree, and diameter of G. One consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)^2/3) vertices are fixed in every untangling of δ.     

On the number of cycles of length k in a maximal planar graph

Let G be a maximal planar graph with p vertices, and let C_k(G) denote the number of cycles of length k in G. We first present tight bounds for C₃(G) and C₄(G) in terms of p. We then give bounds for C_k(G) when 5 ≤ k ≤ p, and consider in particular bounds for C_p(G), in terms of p. Some conjectures and unsolved problems are stated.     

Some Algebraic Methods for Calculating the Number of Colorings of a Graph

With an arbitrary graph G having n vertices and m edges, and with an arbitrary natural number p, we associate in a natural way a polynomial R(x ₁,...,x _n) with integer coefficients such that the number of colorings of the vertices of the graph G in p colors is equal to p ^m-n R(0,...,0). Also with an arbitrary maximal planar graph G, we associate several polynomials with integer coefficients such that the number of colorings of the edges of the graph G in 3 colors can be calculated in several ways via the coefficients of each of these polynomials. Bibliography: 2 titles.     

On planar hypohamiltonian graphs

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for every integer n≥N there exists a planar hypohamiltonian/hypotraceable graph on n vertices. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 55‐68, 2011     

Embedding Planar Graphs at Fixed Vertex Locations

 Let G be a planar graph of n vertices, v ₁,…,v _n , and let {p ₁,…,p _n } be a set of n points in the plane. We present an algorithm for constructing in O(n ²) time a planar embedding of G, where vertex v _i is represented by point p _i and each edge is represented by a polygonal curve with O(n) bends (internal vertices). This bound is asymptotically optimal in the worst case. In fact, if G is a planar graph containing at least m pairwise independent edges and the vertices of G are randomly assigned to points in convex position, then, almost surely, every planar embedding of G mapping vertices to their assigned points and edges to polygonal curves has at least m/20 edges represented by curves with at least m/40³ bends. Received: May 24, 1999 Final version received: April 10, 2000     

Planar Hypohamiltonian Graphs on 40 Vertices

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer‐aided generation of certain families of planar graphs with girth 4 and a fixed number of 4‐faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.     

Near-proper vertex 2-colorings of sparse graphs

A graph G is (2, 1)-colorable if its vertices can be partitioned into subsets V ₁ and V ₂ such that each component in G[V ₁] contains at most two vertices while G[V ₂] is edgeless. We prove that every graph with maximum average degree mad(G) < 7/3 is (2, 1)-colorable. It follows that every planar graph with girth at least 14 is (2, 1)-colorable. We also construct a planar graph G _n with mad (G _n ) = (18n − 2)/(7n − 1) that is not (2, 1)-colorable.     

One-way infinite hamiltonian paths in infinite maximal planar graphs

A one-way infinite Hamiltonian path is constructed in an infinite 4-connected VAP-free maximal planar graph containing one or two vertices of infinite degree. Combining this result and that of R. HALIN who investigated the structure of such graphs, we conclude that such a path always exists in every infinite 4-connected maximal planar graph with exactly one end, which is an extension of H. WHITNEY'S theorem to infinite graphs.     

Acrylic improper colorings of graphs

In this article, we introduce the new notion of acyclic improper colorings of graphs. An improper coloring of a graph is a vertex-coloring in which adjacent vertices are allowed to have the same color, but each color class V_i satisfies some condition depending on i. Such a coloring is acyclic if there are no alternating 2-colored cycles. We prove that every outerplanar graph can be acyclically 2-colored in such a way that each monochromatic subgraph has degree at most five and that this result is best possible. For planar graphs, we prove some negative results and state some open problems. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 97–107, 1999     

The topological structure of scaling limits of large planar maps

We discuss scaling limits of large bipartite planar maps. If p≥2 is a fixed integer, we consider, for every integer n≥2, a random planar map M _n which is uniformly distributed over the set of all rooted 2p-angulations with n faces. Then, at least along a suitable subsequence, the metric space consisting of the set of vertices of M _n , equipped with the graph distance rescaled by the factor n ^-1/4, converges in distribution as n→∞ towards a limiting random compact metric space, in the sense of the Gromov–Hausdorff distance. We prove that the topology of the limiting space is uniquely determined independently of p and of the subsequence, and that this space can be obtained as the quotient of the Continuum Random Tree for an equivalence relation which is defined from Brownian labels attached to the vertices. We also verify that the Hausdorff dimension of the limit is almost surely equal to 4.     

On the number of cycles of length 4 in a maximal planar graph

Let p and C₄ (G) be the number of vertices and the number of 4-cycles of a maximal planar graph G, respectively. Hakimi and Schmeichel characterized those graphs G for which C₄ (G) = 1/2(p² + 3p - 22). This characterization is correct if p ≥ 9. However, for p = 7 or 8, there is exactly one other graph which violates the theorem in the sense that the upper bound of C₄ (G) is also attained.     

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.     

A class of self-complementary vertex-transitive digraphs

We characterize the class of self-complementary vertex-transitive digraphs on a prime number p of vertices. Using this, we enumerate (i) self-complementary strongly vertex-transitive digraphs on p vertices, (ii) self-complementary vertex-transitive digraphs on p vertices, (iii) self-complementary vertex-transitive graphs on p vertices. Finally it is shown that every self-complementary vertex-transitive digraph on p vertices is either a tournament or a graph.     

Covering a graph by topological complete subgraphs

Every graph onn vertices can be covered byex(n, TK ₄ ) =2n – 3 TK ₄ -subgraphs and edges. A similar result might hold for arbitrary topological (complete) subgraphs as indicated by the following result: Every graph onn vertices can be covered by 65ex(n, TK _p )TK _p -subgraphs and edges. IfH is a connected graph (|H| 3) then every graph onn vertices can be covered by 400ex(n, TH) TH-subgraphs and edges. Similar questions for coverings by odd and even cycles are also considered.This author's work was done while he was a guest at the Hungarian Academy of Sciences.     

Cycle Lengths in Hamiltonian Graphs with a Pair of Vertices Having Large Degree Sum

A graph of order n is said to be pancyclic if it contains cycles of all lengths from three to n. Let G be a Hamiltonian graph and let x and y be vertices of G that are consecutive on some Hamiltonian cycle in G. Hakimi and Schmeichel showed (J Combin Theory Ser B 45:99–107, 1988) that if d(x) + d(y) ≥ n then either G is pancyclic, G has cycles of all lengths except n − 1 or G is isomorphic to a complete bipartite graph. In this paper, we study the existence of cycles of various lengths in a Hamiltonian graph G given the existence of a pair of vertices that have a high degree sum but are not adjacent on any Hamiltonian cycle in G.