New constructions of hypohamiltonian and hypotraceable graphs

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14].     

A planar hypohamiltonian graph with 48 vertices

We present a planar hypohamiltonian graph on 48 vertices, and derive some consequences. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 338–342, 2007     

Cubic vertices in planar hypohamiltonian graphs

Thomassen showed in 1978 that every planar hypohamiltonian graph contains a cubic vertex. Equivalently, a planar graph with minimum degree at least 4 in which every vertex-deleted subgraph is hamiltonian, must be itself hamiltonian. By applying work of Brinkmann and the author, we extend this result in three directions. We prove that (i) every planar hypohamiltonian graph contains at least four cubic vertices, (ii) every planar almost hypohamiltonian graph contains a cubic vertex, which is not the exceptional vertex (solving a problem of the author raised in J. Graph Theory [79 (2015) 63–81]), and (iii) every hypohamiltonian graph with crossing number 1 contains a cubic vertex. Furthermore, we settle a recent question of Thomassen by proving that asymptotically the ratio of the minimum number of cubic vertices to the order of a planar hypohamiltonian graph vanishes.     

Infinitely many planar cubic hypohamiltonian graphs of girth 5

A graph G is hypohamiltonian if G is non‐hamiltonian and for every vertex v in G, the graph is hamiltonian. McKay asked in [J. Graph Theory 85 (2017) 7–11] whether infinitely many planar cubic hypohamiltonian graphs of girth 5 exist. We settle this question affirmatively.     

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 hypohamiltonian graphs

Herz, Duby and Vigué [9] conjectured that every hypohamiltonian graph has girth 5. In the present note hypohamiltonian graphs of girth 3 and 4 are described. Also two conjectures on hypohamiltonian graphs made by Bondy and Chvátal, respectively, are disproved.     

On k-ordered Hamiltonian graphs

A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999     

Leaf‐Critical and Leaf‐Stable Graphs

The minimum leaf number ml(G) of a connected graph G is defined as the minimum number of leaves of the spanning trees of G if G is not hamiltonian and 1 if G is hamiltonian. We study nonhamiltonian graphs with the property for each or for each . These graphs will be called ‐leaf‐critical and l‐leaf‐stable, respectively. It is far from obvious whether such graphs exist; for example, the existence of 3‐leaf‐critical graphs (that turn out to be the so‐called hypotraceable graphs) was an open problem until 1975. We show that l‐leaf‐stable and l‐leaf‐critical graphs exist for every integer , moreover for n sufficiently large, planar l‐leaf‐stable and l‐leaf‐critical graphs exist on n vertices. We also characterize 2‐fragments of leaf‐critical graphs generalizing a lemma of Thomassen. As an application of some of the leaf‐critical graphs constructed, we settle an open problem of Gargano et al. concerning spanning spiders. We also explore connections with a family of graphs introduced by Grünbaum in correspondence with the problem of finding graphs without concurrent longest paths.     

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.     

A generalization of Tutte’s theorem on Hamiltonian cycles in planar graphs

In 1956, W.T. Tutte proved that a 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. We prove that a planar graph G has a cycle containing a given subset X of its vertex set and any two prescribed edges of the subgraph of G induced by X if |X|≥3 and if X is 4-connected in G. If X=V(G) then Sanders’ result follows.     

On stable cutsets in claw-free graphs and planar graphs

A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let $K_4$ and $K_{1,3}$ (claw) denote the complete (bipartite) graph on 4 and $1+3$ vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a $K_4$-free graph admits a stable cutset. Here we describe algorithms deciding in polynomial time whether a claw-free graph with maximum degree at most four or whether a (claw, $K_4$)-free graph admits a stable cutset. As a by-product we obtain that the stable cutset problem is polynomially solvable for claw-free planar graphs, and also for planar line graphs.Thus, the computational complexity of the stable cutset problem is completely determined for claw-free graphs with respect to degree constraint, and for claw-free planar graphs. Moreover, we prove that the stable cutset problem remains NP-complete for $K_4$-free planar graphs with maximum degree five.     

Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs

In 1956, W.T. Tutte proved that every 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. It is shown that Sanders’ result is best possible by constructing 4-connected maximal planar graphs with three edges a large distance apart such that any hamiltonian cycle misses one of them. If the maximal planar graph is 5-connected then such a construction is impossible.     

Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.     

Cubic planar hamiltonian graphs of various types

Let U be the set of cubic planar hamiltonian graphs, A the set of graphs G in U such that G-v is hamiltonian for any vertex v of G, B the set of graphs G in U such that G-e is hamiltonian for any edge e of G, and C the set of graphs G in U such that there is a hamiltonian path between any two different vertices of G. With the inclusion and/or exclusion of the sets A,B, and C, U is divided into eight subsets. In this paper, we prove that there is an infinite number of graphs in each of the eight subsets.     

On 2-walks in chordal planar graphs

A 2-walk is a closed spanning trail which uses every vertex at most twice. A graph is said to be chordal if each cycle different from a 3-cycle has a chord. We prove that every chordal planar graph G with toughness has a 2-walk.     

On graphs with the largest Laplacian index

Let G be a connected simple graph on n vertices. The Laplacian index of G, namely, the greatest Laplacian eigenvalue of G, is well known to be bounded above by n. In this paper, we give structural characterizations for graphs G with the largest Laplacian index n. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on n and k for the existence of a k-regular graph G of order n with the largest Laplacian index n. We prove that for a graph G of order n ⩾ 3 with the largest Laplacian index n, G is Hamiltonian if G is regular or its maximum vertex degree is Δ(G) = n/2. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results. The first author is supported by NNSF of China (No. 10771080) and SRFDP of China (No. 20070574006). The work was done when Z. Chen was on sabbatical in China.     

On 3-colorable planar graphs without prescribed cycles

In this paper we prove that every planar graph without cycles of length 4, 5, 6 and 8 is 3-colorable.