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.     

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.     

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

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.     

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.     

Heavy cycles passing through some specified vertices in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex υ is called the weighted degree of υ. The weight of a cycle is defined as the sum of the weights of its edges. In this paper, we prove that: (1) if G is a 2‐connected weighted graph such that the minimum weighted degree of G is at least d, then for every given vertices x and y, either G contains a cycle of weight at least 2d passing through both of x and y or every heaviest cycle in G is a hamiltonian cycle, and (2) if G is a 2‐connected weighted graph such that the weighted degree sum of every pair of nonadjacent vertices is at least s, then for every vertex y, G contains either a cycle of weight at least s passing through y or a hamiltonian cycle. AMS classification: 05C45 05C38 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Decomposition of cubic graphs related to Wegner’s conjecture

Thomassen formulated the following conjecture: Every 3-connected cubic graph has a red–blue vertex coloring such that the blue subgraph has maximum degree 1 (that is, it consists of a matching and some isolated vertices) and the red subgraph has minimum degree at least 1 and contains no 3-edge path. We prove the conjecture for Generalized Petersen graphs.We indicate that a coloring with the same properties might exist for any subcubic graph. We confirm this statement for all subcubic trees.     

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.     

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     

Spanning trees without adjacent vertices of degree 2

Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number $d$ such that every graph of minimum degree at least $d$ contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.     

Schrijver图SG(2k+2,k)的Hamilton性

通过图G的每个顶点的路称为Hamilton路,通过图G的每个顶点的圈称为Hamilton圈,具有Hamilton圈的图G称为Hamilton图.1952年Dirac曾得到关于Hamilton图一个充分条件的结论:图G有n个顶点,如果每个顶点υ满足:d(υ)≥n/2,则图G是Hamilton图.本文研究了Schrijver图SG(2k+2,k)的Hamilton性,采用寻找Hamilton圈的方法得出了Schrijver图SG(2k+2,k)是Hamilton图.     

On the number of hamiltonian cycles in a maximal planar graph

We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on p vertices. In particular, we construct a p-vertex maximal planar graph containing exactly four Hamiltonian cycles for every p ≥ 12. We also prove that every 4-connected maximal planar graph on p vertices contains at least p/(log₂ p) Hamiltonian cycles.     

Every graph occurs as an induced subgraph of some hypohamiltonian graph

We prove the titular statement. This settles a problem of Chvátal from 1973 and encompasses earlier results of Thomassen, who showed it for K₃, and Collier and Schmeichel, who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph.     

一类直径为2的极大平面图的Mostar指数

图G的Mostar指数定义为Mo(G)=∑uv∈Ε(G)|nu-nv|,其中nu表示在G中到顶点u的距离比到顶点v的距离近的顶点个数,nv表示到顶点v的距离比到顶点u的距离近的顶点个数.若一个图G的任两点之间的距离至多为2,且不是完全图,则称G是一个直径为2的图.已知直径为2点数至少为4的极大平面图的最小度为3或4.本文研究了直径为2且最小度为4的极大平面图的Mostar指数.具体说,若G是一个点数为n,直径为2,最小度为4的极大平面图,则(1)当n≤12时,Mostar指数被完全确定;(2)当n≥13时,4/3n2-44/3n+94/3≤Mo(G)≤2n2-16n+24,且达到上,下界的极图同时被找到.     

Contractible Subgraphs,Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks

We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is hamiltonian), by Thomassen (every 4-connected line graph is hamiltonian) and by Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent with the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.We use a refinement of the contractibility technique which was introduced by Ryjáček and Schelp in 2003 as a common generalization and strengthening of the reduction techniques by Catlin and Veldman and of the closure concept introduced by Ryjáček in 1997.     

On the hamiltonian path graph of a graph

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and v are adjacent if and only if F contains a hamiltonian u ? v path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian graphs isomorphic to their hamiltonian path graphs is presented. Next, the maximum size of a hamiltonian graph F of given order such that K?_d ? H(F) is determined. Finally, it is shown that if the degree sum of the endvertices of a hamiltonian path in a graph F with at least five vertices is at least |V(F)| + t(t ? 0), then H(F) contains a complete subgraph of order t + 4.     

Every 4-Connected Line Graph of a Planar Graph is Hamiltonian

Let G be a graph withE(G) $#x2260;ø. The line graph of G, written L(G) hasE(G) as its vertex set, where two vertices are adjacent in L(G) if and only if the corresponding edges are adjacent inG. Thomassen conjectured that all 4-connected line graphs are hamiltonian [2]. We show that this conjecture holds for planar graphs.     

List precoloring extension in planar graphs

A celebrated result of Thomassen states that not only can every planar graph be colored properly with five colors, but no matter how arbitrary palettes of five colors are assigned to vertices, one can choose a color from the corresponding palette for each vertex so that the resulting coloring is proper. This result is referred to as 5-choosability of planar graphs. Albertson asked whether Thomassen’s theorem can be extended by precoloring some vertices which are at a large enough distance apart in a graph. Here, among others, we answer the question in the case when the graph does not contain short cycles separating precolored vertices and when there is a “wide” Steiner tree containing all the precolored vertices.     

An approximation algorithm for the hamiltonian walk problem on maximal planar graphs

A hamiltonian walk of a graph is a shortest closed walk that passes through every vertex at least once, and the length is the total number of traversed edges. The hamiltonian walk problem in which one would like to find a hamiltonian walk of a given graph is NP-complete. The problem is a generalized hamiltonian cycle problem and is a special case of the traveling salesman problem. Employing the techniques of divide-and-conquer and augmentation, we present an approximation algorithm for the problem on maximal planar graphs. The algorithm finds, in O(p²) time, a closed spanning walk of a given arbitrary maximal planar graph, and the length of the obtained walk is at most $\text{3}\text{2}$(p ? 3) if the graph has p (≥ 9) vertices. Hence the worst-case bound is $\text{3}\text{2}$.     

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.