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].     

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     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.     

Planar and infinite hypohamiltonian and hypotraceable graphs

Chvátal raised the question whether or not planar hypohamiltonian graphs exist and Grünbaum conjectured the nonexistence of such graphs. We shall describe an infinite class of planar hypohamiltonian graphs and infinite classes of planar hypotraceable graphs of connectivity two (resp. three). Infinite hypohamiltonian (resp. htpotraceable) graphs are also described. It is shown how the study of infinite hypotraceable graphs leads to a new infinite family of finite hypotraceable graphs.     

Planar cubic hypohamiltonian and hypotraceable graphs

Infinite families of planar cubic hypohamiltonian and hypotraceable graphs are described and these are used to prove that the maximum degree and the maximum number of edges in a hypohamiltonian graph with n vertices are approximately $\text{n}\text{2}$ and $\text{n}{}^2\text{4}$, respectively. Also, the possible order of a cubic hypohamiltonian graph is determined.     

On Hypohamiltonian and Almost Hypohamiltonian Graphs

A graph G is almost hypohamiltonian if G is non‐hamiltonian, there exists a vertex w such that is non‐hamiltonian, and for any vertex the graph is hamiltonian. We prove the existence of an almost hypohamiltonian graph with 17 vertices and of a planar such graph with 39 vertices. Moreover, we find a 4‐connected almost hypohamiltonian graph, while Thomassen's question whether 4‐connected hypohamiltonian graphs exist remains open. We construct planar almost hypohamiltonian graphs of order n for every . During our investigation we draw connections between hypotraceable, hypohamiltonian, and almost hypohamiltonian graphs, and discuss a natural extension of almost hypohamiltonicity. Finally, we give a short argument disproving a conjecture of Chvátal (originally disproved by Thomassen), strengthen a result of Araya and Wiener on cubic planar hypohamiltonian graphs, and mention open problems.     

An Infinite Family of Planar Hypohamiltonian Oriented Graphs

Carsten Thomassen asked in 1976 whether there exists a planar hypohamiltonian oriented graph. We answer his question by presenting an infinite family of planar hypohamiltonian oriented graphs, the smallest of which has order 9. A computer search showed that 9 is the smallest possible order of a hypohamiltonian oriented graph.     

Mapping Planar Graphs into Projective Cubes

Projective cubes are obtained by identifying antipodal vertices of hypercubes. We introduce a general problem of mapping planar graphs into projective cubes. This question, surprisingly, captures several well‐known theorems and conjectures in the theory of planar graphs. As a special case , we prove that the Clebsch graph, a triangle‐free graph on 16 vertices, is the smallest triangle‐free graph to which every triangle‐free planar graph admits a homomorphism.     

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.     

A note on the smallest connected non-traceable cubic bipartite planar graph

A graph is traceable if it contains a Hamiltonian path. We present a connected non-traceable cubic bipartite planar graph with 52 vertices and prove that there are no smaller such graphs.     

Planar graphs without 4‐cycles adjacent to 3‐cycles are list vertex 2‐arborable

It is known that not all planar graphs are 4‐choosable; neither all of them are vertex 2‐arborable. However, planar graphs without 4‐cycles and even those without 4‐cycles adjacent to 3‐cycles are known to be 4‐choosable. We extend this last result in terms of covering the vertices of a graph by induced subgraphs of variable degeneracy. In particular, we prove that every planar graph without 4‐cycles adjacent to 3‐cycles can be covered by two induced forests. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 234–240, 2009     

Almost self-centered graphs

The center of a graph is the set of vertices with minimum eccentricity. Graphs in which all vertices are central are called self-centered graphs. In this paper almost self-centered (ASC) graphs are introduced as the graphs with exactly two non-central vertices. The block structure of these graphs is described and constructions for generating such graphs are proposed. Embeddings of arbitrary graphs into ASC graphs are studied. In particular it is shown that any graph can be embedded into an ASC graph of prescribed radius. Embeddings into ASC graphs of radius two are studied in more detail. ASC index of a graph G is introduced as the smallest number of vertices needed to add to G such that G is an induced subgraph of an ASC graph.     

Infinite paths in planar graphs II,structures and ladder nets

A graph is k‐indivisible, where k is a positive integer, if the deletion of any finite set of vertices results in at most k – 1 infinite components. In 1971, Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if and only if it is 3‐indivisible. In this paper, we prove a structural result for 2‐indivisible infinite planar graphs. This structural result is then used to prove Nash‐Williams conjecture for all 4‐connected 2‐indivisible infinite planar graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 247–266, 2005     

New families of hypohamiltonian graphs

We construct three new infinite families of hypohamiltonian graphs having respectively 3k+1 vertices (k?3), 3k vertices (k?5) and 5k vertices (k?4); in particular, we exhibit a hypohamiltonian graph of order 19 and a cubic hypohamiltonian graph of order 20, the existence of which was still in doubt. Using these families, we get a lower bound for the number of non-isomorphic hypohamiltonian graphs of order 3k and 5k. We also give an example of an infinite graph G having no two-way infinite hamiltonian path, but in which every vertex-deleted subgraph G - x has such a path.     

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     

Outerplanar and Planar Oriented Cliques

The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .     

On Non‐Hamiltonian Graphs for which every Vertex‐Deleted Subgraph Is Traceable

We call a graph G a platypus if G is non‐hamiltonian, and for any vertex v in G, the graph is traceable. Every hypohamiltonian and every hypotraceable graph is a platypus, but there exist platypuses that are neither hypohamiltonian nor hypotraceable. Among other things, we give a sharp lower bound on the size of a platypus depending on its order, draw connections to other families of graphs, and solve two open problems of Wiener. We also prove that there exists a k‐connected platypus for every .     

Hamiltonian graphs of given order and minimum algebraic connectivity

In this paper, we study the algebraic connectivity of a Hamiltonian graph, and determine all Hamiltonian graphs whose algebraic connectivity attain the minimum among all Hamiltonian graphs on n vertices.     

Hamilton cycle rich two‐factorizations of complete graphs

For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph K_n of order n. For example, it is shown that for all odd n ≥ 11, K_n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph K_n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.     

Infinite families of 2-hypohamiltonian/2-hypotraceable oriented graphs

A digraph D of order n is r-hypohamiltonian (respectively r-hypotraceable) for some positive integer r < n ? 1 if D is nonhamiltonian (nontraceable) and the deletion of any r of its vertices leaves a hamiltonian (traceable) digraph. A 1-hypohamiltonian (1-traceable) digraph is simply called hypohamiltonian (hypotraceable). Although hypohamiltonian and hypotraceable digraphs are well-known and well-studied concepts, we have found no mention of r-hypohamiltonian or r-hypotraceable digraphs in the literature for any r > 1. In this paper we present infinitely many 2-hypohamiltonian oriented graphs and use these to construct infinitely many 2-hypotraceable oriented graphs. We also discuss an interesting connection between the existence of r-hypotraceable oriented graphs and the Path Partition Conjecture for oriented graphs.