69. Counting Small Cycle Double Covers (with J. Jooken and B. Seamone)
Submitted.
Abstract
We give an enumerative version of Seyffarth's theorem on small cycle double covers in planar 4-connected graphs. We then count cycle double covers of certain sizes in antiprisms and related graphs, giving a surprisingly small upper bound. Thereafter we treat cubic graphs, strengthening a lemma of Hušek and Šámal on the enumeration of cycle double covers, and, motivated by a conjecture of Bondy, give an alternative proof of the result that every planar 2-connected cubic graph on n > 4 vertices has a cycle double cover of size at most n/2. Some of our results are accompanied by a version thereof for cycle double covers containing no cycle twice.
68. Non-Hamiltonian Cartesian products of two even dicycles (with K. Noguchi)
Submitted.
Abstract
In this note it is proven that there exist infinitely many positive integers a and b such that the Cartesian product of a directed cycle of length 2a and a directed cycle of length 2b is non-Hamiltonian. In particular, the Cartesian product of an 880-dicycle and a 4368-dicycle is non-Hamiltonian. We also prove that there is no such graph on fewer than 880 × 4368 = 3,843,840 vertices, which is rather astonishing.
67. HIST-Critical Graphs and Malkevitch’s Conjecture (with J. Goedgebeur, K. Noguchi, and J. Renders)
Submitted.
Abstract
In a given graph, a HIST is a spanning tree without 2-valent vertices. Motivated by developing a better understanding of HIST-free graphs, i.e. graphs containing no HIST, in this article's first part we study HIST-critical graphs, i.e. HIST-free graphs in which every vertex-deleted subgraph does contain a HIST (e.g. a triangle). We give an almost complete characterisation of the orders for which these graphs exist and present an infinite family of planar examples which are 3-connected and in which nearly all vertices are 4-valent. This leads naturally to the second part in which we investigate planar 4-regular graphs with and without HISTs, motivated by a conjecture of Malkevitch, which we computationally verify up
to order 22. First we enumerate HISTs in antiprisms, whereafter we present planar 4-regular graphs with and without HISTs, obtained via line graphs.
Links
arXiv:2401.04554
66. Spanning trees for many different numbers of leaves (with K. Noguchi)
Submitted.
Abstract
Let G be a connected graph and L(G) the set of all integers k such that G contains a spanning tree with exactly k leaves. We show that for a connected graph G, the set L(G) is contiguous. It follows from work of Chen, Ren, and Shan that every connected and locally connected n-vertex graph – this includes triangulations – has a spanning tree with at least n/2 + 1 leaves, so by a classic theorem of Whitney and our result, in any plane 4-connected n-vertex triangulation one can find for any integer k which is at least 2 and at most n/2 + 1 a spanning tree with exactly k leaves (and each of these trees can be constructed in polynomial time). We also prove that there exist infinitely many n such that there is a plane 4-connected n-vertex triangulation containing a spanning tree with 2n/3 leaves, but no spanning tree with more than 2n/3 leaves.
Links
arXiv:2312.13674
65. Counting cycles in planar triangulations (with O. S. Lo)
Submitted.
Abstract
We investigate the minimum number of cycles of specified lengths in planar n-vertex triangulations G. It is proven that this number is Ω(n) for any cycle length at most 3 + max { rad(G*), ((n − 3)/2)^{log32} }, where rad(G*) denotes the radius of the triangulation's dual, which is at least logarithmic but can be linear in the order of the triangulation. We also show that there exist planar hamiltonian n-vertex triangulations containing O(n) many k-cycles for any k ∈ { n − $\sqrt[5]{\mathrm{n}}$, ..., $$n }. Furthermore, we prove that planar 4-connected n-vertex triangulations contain Ω(n) many k-cycles for every k ∈ { 3, ..., n }, and that, under certain additional conditions, they contain Ω(n^{2}) k-cycles for many values of k, including n.
Links
arXiv:2210.01190
64. On the space of finite connected graphs endowed with the Gromov-Hausdorff metric (with T. I. Zamfirescu)
Submitted.
Abstract
In the seventies, Mikhail Gromov introduced a natural concept for measuring distance between metric spaces. We use his concept, endowing the space of all finite connected graphs with the Gromov-Hausdorff metric, and prove a series of observations concerning this space. Thus, we also investigate here graphs of graphs.
63. Shortness parameters of polyhedral graphs with few distinct vertex degrees (with O. S. Lo, J. M. Schmidt, and N. Van Cleemput)
Submitted.
Abstract
We devise several new upper bounds for shortness parameters of regular polyhedra and of the polyhedra that have two vertex degrees, and relate these to each other. Grünbaum and Walther showed that quartic polyhedra have shortness exponent at most log 22/log 23. This was subsequently improved by Harant to log 16/log 17, which holds even when all faces are either triangles or of length k, for infinitely many k. We complement Harant's result by strengthening the Grünbaum-Walther bound to log 4/log 5, and showing that this bound even holds for the family of quartic polyhedra with faces of length at most 7. Furthermore, we prove that for every 4 ≤ k ≤ 8 the shortness exponent of the polyhedra having only vertices of degree 3 or k is at most log 5/log 7. Motivated by work of Ewald and Reynolds, we show that polyhedral quadrangulations with maximum degree at most 5 have shortness coefficient at most
30/37. Finally, we define path analogues for shortness parameters, and propose first dependencies between these measures.
62. Few hamiltonian cycles in graphs with one or two vertex degrees (with J. Goedgebeur, J. Jooken, O. S. Lo, and B. Seamone)
To appear in: Mathematics of Computation.
Abstract
Inspired by Sheehan's conjecture that no 4-regular graph contains exactly one hamiltonian cycle, we prove results on hamiltonian cycles in regular graphs and nearly regular graphs. We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct and complement Haythorpe's computational enumerative results from [Experim. Math. 27 (2018) 426–30]. Thereafter, we use the Lovász Local Lemma to extend Thomassen's independent dominating set method. This extension allows us to find a second hamiltonian cycle that inherits linearly many edges from the first hamiltonian cycle. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen by showing that for k ∊ { 5, 6 } there exist infinitely many k-regular hamiltonian graphs having no independent dominating set with respect to a prescribed hamiltonian cycle. Motivated by an observation of Aldred and Thomassen, we prove that for every κ ∊ { 2, 3 } and any positive integer k, there are infinitely many non-regular graphs of connectivity κ containing exactly one hamiltonian cycle and in which every vertex has degree 3 or 2k.
Links
arXiv:2211.08105
DOI: 10.1090/mcom/3943
61. A Graph Called Harmony
To appear in: Elemente der Mathematik.
Abstract
The graph6 format is for storing graphs in a compact manner, using only printable ASCII characters—these include (but are not limited to) the letters in the English alphabet, in both lower and upper case. While the vast majority of graphs have graph6 strings such as IheA@GUAo (this yields Petersen's graph), there exist graphs whose graph6 strings are identical to words in the English language. The purpose of this note is to present an example of such a string, as well as a characterisation of words that appear as graph6 strings.
Links
DOI: 10.4171/EM/520
60. On non-hamiltonian polyhedra without cubic vertices and their vertex-deleted subgraphs (with J. Goedgebeur and T. Gringore)
To appear in: Discussiones Mathematicae Graph Theory.
Abstract
Thomassen proved in 1978 that if in an n-vertex planar graph G whose minimum degree is at least 4 all vertex-deleted subgraphs of G are hamiltonian, then G is hamiltonian. It was recently shown that in the preceding sentence, “all” can be replaced by “at least n − 5”. In this note we prove that, if 3-connectedness is assumed, it cannot be replaced by n − 24 (or any other integer greater than 24). The exact threshold remains unknown. We show that the same conclusion holds for triangulations and use computational means to prove that, under a natural restriction, this result is best possible.
Links
DOI: 10.7151/dmgt.2514
59. Generation and new infinite families of K_{2}-hypohamiltonian graphs (with J. Goedgebeur and J. Renders)
Discrete Math. 347, Iss. 7 (2024) Article Nr. 113981.
Abstract
We present an algorithm which can generate all pairwise non-isomorphic K_{2}-hypohamiltonian graphs, i.e. non-hamiltonian graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, of a given order. We introduce new bounding criteria especially designed for K_{2}-hypohamiltonian graphs, allowing us to improve upon earlier computational results. Specifically, we characterise the orders for which K_{2}-hypohamiltonian graphs exist and improve existing lower bounds on the orders of the smallest planar and the smallest bipartite K_{2}-hypohamiltonian graphs. Furthermore, we describe a new operation for creating K_{2}-hypohamiltonian graphs that preserves planarity under certain conditions and use it to prove the existence of a planar K_{2}-hypohamiltonian graph of order n for every integer n ≥ 134. Additionally, motivated by a theorem of Thomassen on hypohamiltonian graphs, we show the existence K_{2}-hypohamiltonian graphs with large maximum degree and size.
Links
arXiv:2311.10593
DOI: 10.1016/j.disc.2024.113981
58. Domination of triangulated discs and maximal outerplanar graphs (with J. Renders and Shin-ichi Tokunaga)
Appl. Math. Comput. 473 (2024) Article Nr. 128648.
Abstract
Given an infinite family of graphs, its domination ratio is the smallest real k such that for every large enough graph in the family, the ratio between its domination number and order is at most k. We present bounds for the domination ratios of various families of triangulated discs. For instance, it is shown that the domination ratio of triangulated discs of minimum degree 3 is at least 3/10, thereby disproving a conjecture of Tokunaga. We also give a natural extension of a theorem on the domination number of maximal outerplane graphs, proven by Campos and Wakabayashi, and
independently Tokunaga. Motivated by the Matheson-Tarjan Conjecture, we discuss observations on dominating triangulations via Jackson-Yu decomposition trees as well as an approach on how to efficiently dominate, given a triangulation, many large subtriangulations thereof. Throughout the paper, results are accompanied by computational experiments.
Links
DOI: 10.1016/j.amc.2024.128648
57. K_{2}-hamiltonian graphs: II (with J. Goedgebeur, J. Renders, and G. Wiener)
J. Graph Theory 105, Iss. 4 (2024) 580–611.
Abstract
In this paper, we use theoretical and computational tools to continue our investigation of K_{2}-hamiltonian graphs, that is, graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, and their interplay with K_{1}-hamiltonian graphs, that is, graphs in which every vertex-deleted subgraph is hamiltonian. Perhaps surprisingly, there exist graphs that are both K_{1}- and K_{2}-hamiltonian, yet non-hamiltonian, for example, the Petersen graph. Grünbaum conjectured that every planar K_{1}-hamiltonian graph must itself be hamiltonian; Thomassen disproved this conjecture. Here we show that even planar graphs that are both K_{1}- and K_{2}-hamiltonian need not be hamiltonian, and that the number of such graphs grows at least exponentially. Motivated by results of Aldred, McKay, and Wormald, we determine for every integer n that is not 14 or 17 whether there exists a K_{2}-hypohamiltonian, that is non-hamiltonian and K_{2}-hamiltonian, graph of order n, and characterise all orders for which such cubic graphs and such snarks exist. We also describe the smallest cubic planar graph which is K_{2}-hypohamiltonian, as well as the smallest planar K_{2}-hypohamiltonian graph of girth 5. We conclude with open problems and by correcting two inaccuracies from the first article.
Links
arXiv:2311.05262
DOI: 10.1002/jgt.23057
56. On a conjecture of Grünbaum on longest cycles
Europ. J. Combin. 114 (2023) Article 103791.
Abstract
Grünbaum conjectured that for any integer k ≥ 2, there exists no n-vertex graph G of circumference n − k in which the removal of any k vertices from G yields a hamiltonian graph. We show that for any positive integers c and k there is an infinite family of c-connected graphs of circumference k less than their order, in which the limit (as the graphs' order tends to infinity) of the ratio between the number of k-vertex sets whose removal yields a hamiltonian graph and the number of all k-vertex sets is 1. Motivated by a question of Katona, Kostochka, Pach, and Stechkin, it is proven that there exists an infinite family of non-hamiltonian graphs of increasing diameter d in which the removal of any two vertices at distance 1 or any distance at least (d + 6)/2 yields a hamiltonian graph.
Links
Full text as PDF
DOI: 10.1016/j.ejc.2023.103791
55. On the hamiltonicity of a planar graph and its vertex-deleted subgraphs
J. Graph Theory 102, Iss. 1 (2023) 180–93.
Abstract
Tutte proved that every planar 4-connected graph is hamiltonian. Thomassen showed that the same conclusion holds for the superclass of planar graphs with minimum degree at least 4 in which all vertex-deleted subgraphs are hamiltonian. We here prove that if in a planar n-vertex graph with minimum degree at least 4 at least n − 5 vertex-deleted subgraphs are hamiltonian, then the graph contains two hamiltonian cycles, but that for every c < 1 there exists a non-hamiltonian polyhedral n-vertex graph with minimum degree at least 4 containing c n hamiltonian vertex-deleted subgraphs. Furthermore, we study the hamiltonicity of planar triangulations and their vertex-deleted subgraphs as well as Bondy's meta-conjecture, and prove that a polyhedral graph with minimum degree at least 4 in which all vertex-deleted subgraphs are traceable, must itself be traceable.
Links
Full text as PDF
DOI: 10.1002/jgt.22864
54. Tight cycle spectrum gaps of cubic 3-connected toroidal graphs (with O. S. Lo)
Discrete Math. 346, Iss. 1 (2023) 113170.
Abstract
This note complements results on cycle spectra of planar graphs by investigating the toroidal case. Let k ≥ 3 be an integer and G a cubic graph polyhedrally embedded on the torus with circumference at least k. For k = 3, it follows from Euler's formula that G has some (facial) cycle of length in [3, 6]. For k = 4 or 5, we show that G contains a cycle whose length lies in the interval [k, 12]; and for k > 5, we show that the same holds for the interval [k, 2k + 4]. This is best possible for all k ≥ 4. On the other hand, for any non-negative integer γ there exist 2-connected cubic graphs G of genus γ, arbitrarily large face-width, and with arbitrarily large gaps in their cycle spectrum. The behaviour of cycle spectrum gaps of graphs polyhedrally embedded on surfaces of genus greater than 1 remains largely unknown.
Links
Full text as PDF
DOI: 10.1016/j.disc.2022.113170
53. The Connectivity of the Dual (with D. Bokal and G. Brinkmann)
J. Graph Theory 101, Iss. 2 (2022) 182–209.
Abstract
The dual of a polyhedron is a polyhedron—or in graph theoretical terms: the dual of a 3-connected plane graph is a 3-connected plane graph. Astonishingly, except for sufficiently large facewidth, not much is known about the connectivity of the dual on higher surfaces. Are the duals of 3-connected embedded graphs of higher genus 3-connected, too? If not: which connectivity guarantees 3-connectedness of the dual? In this article, we give answers to this and related questions. Among other things, we prove that there is no connectivity that for every genus guarantees the 3-connectedness or 2-connectedness of the dual, and give upper bounds for the minimum genus for which (with c > 2) a c-connected embedded graph with a dual that has a 1- or 2-cut can occur. For the torus, we determine exact values for the connectivity needed to guarantee 3- respectively 2-connectivity of the dual. We prove that already on the torus, we need 6-connectedness to guarantee 3-connectedness of the dual and 4-connectedness to guarantee 2-connectedness of the dual. In the last section, we answer a related question by Plummer and Zha on orientable embeddings of highly connected non-complete graphs.
Links
arXiv:1812.08510
DOI: 10.1002/jgt.22819
52. On 2-factors splitting an embedded graph into two plane graphs (with G. Brinkmann and S. Chiers)
Graphs Combin. 38 (2022) Article number: 76.
Abstract
We investigate 2-planarizing 2-factors, i.e. 2-factors of embedded graphs so that cutting along the cycles of the 2-factor we get two plane graphs where the cycles of the 2-factors are a spanning set of face boundaries in each of the graphs. We will give necessary criteria for an abstract graph to have an embedding with a 2-planarizing 2-factor as well as necessary criteria for embedded graphs to have such a 2-factor. Along the way, we discuss to which degree classical results from planar hamiltonicity theory can be extended in our framework. In addition we present computational results on how common 2-planarizing 2-factors are in small cubic graphs.
Links
Full text as PDF
DOI: 10.1007/s00373-022-02473-3
51. Regular graphs with few longest cycles
SIAM J. Discrete Math. 36, Iss. 1 (2022) 755–76.
Abstract
Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant c such that there is an infinite family of 4-regular 4-connected graphs, each containing exactly c hamiltonian cycles. We complement this by proving that the same conclusion holds for planar 4-regular 3-connected graphs, although it does not hold for planar 4-regular 4-connected graphs by a result of Brinkmann and Van Cleemput, and that it holds for 4-regular graphs of connectivity 2 with the constant 144 < c, which we believe to be minimal among all hamiltonian 4-regular graphs of sufficiently large order. We then disprove a conjecture of Haythorpe by showing that for every non-negative integer k there is a 5-regular graph on 26 + 6k vertices with 2^{k+3} · 3^{k+10} hamiltonian cycles. We prove that for every d ≥ 3 there is an infinite family of hamiltonian 3-connected graphs with minimum degree d, with a bounded number of hamiltonian cycles. It is shown that if a 3-regular graph G has a unique longest cycle C, at least two components of G − E(C) have an odd number of vertices on C, and that there exist 3-regular graphs with exactly two such components.
Remarks
On page 766, at the beginning of Section 3, instead of referring to Table 1 one must refer to Table 3 from [J. Goedgebeur, B. Meersman, and C. T. Zamfirescu, Graphs with few Hamiltonian cycles, Math. Comp. 89 (2020) 965–991].
Links
arXiv:2104.10020
DOI: 10.1137/21M1414048
50. Hamiltonian cycles and 1-factors in 5-regular graphs (with N. Van Cleemput)
J. Combin. Theory, Ser. B 154 (2022) 239–61.
Abstract
It is proven that for any integer g ≥ 0 and k ∈ {0, ..., 10}, there exist infinitely many 5-regular graphs of genus g containing a 1-factorisation with exactly k pairs of 1-factors that are perfect, i.e. form a hamiltonian cycle. For g = 0 and k = 10, this settles a problem of Kotzig from 1964. Motivated by Kotzig and Labelle's “marriage” operation, we discuss two gluing techniques aimed at producing graphs of high cyclic edge-connectivity. We prove that there exist infinitely many planar 5-connected 5-regular graphs in which every 1-factorisation has zero perfect pairs. On the other hand, by the Four Colour Theorem and a result of Brinkmann and the first author, every planar 4-connected 5-regular graph satisfying a condition on its hamiltonian cycles has a linear number of 1-factorisations each containing at least one perfect pair. We also prove that every planar 5-connected 5-regular graph satisfying a stronger condition contains a 1-factorisation with at most nine perfect pairs, whence, every such graph admitting a 1-factorisation with ten perfect pairs has at least two edge-Kempe equivalence classes.
Links
arXiv:2008.03173
DOI: 10.1016/j.jctb.2021.12.008
49. Counterexamples to a conjecture of Merker on 3-connected cubic planar graphs with a large cycle spectrum gap
Discrete Math. 345, Iss. 6 (2022) 112824.
Abstract
Merker conjectured that if k ≥ 2 is an integer and G a 3-connected cubic planar graph of circumference at least k, then the set of cycle lengths of G must contain at least one element of the interval [k, 2k+2]. We here prove that for every even integer k ≥ 6 there is an infinite family of counterexamples.
Links
arXiv:2009.00423
DOI: 10.1016/j.disc.2022.112824
48. Planar Hypohamiltonian Oriented Graphs (with A. P. Burger, J. P. de Wet, M. Frick, and N. Van Cleemput)
J. Graph Theory 100, Iss. 1 (2022) 50–68.
Abstract
In 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many n it remained an open question whether planar hypohamiltonian oriented graphs of order n exist. In this paper we develop new methods for constructing hypohamiltonian digraphs, which, combined with efficient graph generation algorithms, enable us to fully characterise the orders for which planar hypohamiltonian oriented graphs exist. Our novel methods also led us to discover the planar hypohamiltonian oriented graph of smallest order and size, as well as infinitely many hypohamiltonian orientations of maximal planar graphs. Furthermore, we answer a question related to a problem of Schiermeyer on vertex degrees in hypohamiltonian oriented graphs, and characterise all the orders for which planar hypotraceable oriented graphs exist.
Links
Full text as PDF
DOI: 10.1002/jgt.22765
47. Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs
Inform. Proc. Lett. 174 (2022) Article 106192.
Abstract
A 2-connected non-hamiltonian graph G is a k-graph if for exactly k < |V(G)| vertices in G, removing such a vertex yields a non-hamiltonian graph. We characterise k-graphs of connectivity 2 and describe structurally interesting examples of such graphs containing no cubic vertex or of minimum degree at least 4, with a special emphasis on the planar case. We prove that there exists a k_{0} such that for every k ≥ k_{0} infinitely many planar k-graphs of connectivity 2 and minimum degree 4 exist. As a variation of a result of Thomassen, we show that certain planar 3-graphs must contain a cubic vertex.
Links
Full text as PDF
DOI: 10.1016/j.ipl.2021.106192
46. 4-regular 4-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles (with C. Thomassen)
Australasian J. Combin. 81, Iss. 2 (2021) 334–8.
Abstract
We prove that there exists an infinite family of 4-regular 4-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles. We do not know if there exists such a family of 5-regular 5-connected Hamiltonian graphs.
Links
Full text as PDF
Journal Link
45. K_{2}-hamiltonian graphs: I
SIAM J. Discrete Math. 35, Iss. 3 (2021) 1706–28.
Abstract
Motivated by a conjecture of Grünbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both dealing with non-hamiltonian n-vertex graphs and their (n − 2)-cycles, we investigate K_{2}-hamiltonian graphs, i.e. graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph. In this first part, we prove structural properties, and show that there exist infinitely many cubic non-hamiltonian K_{2}-hamiltonian graphs, both of the 3-edge-colourable and the non-3-edge-colourable variety. In fact, cubic K_{2}-hamiltonian graphs with chromatic index 4 (such as Petersen's graph) are a subset of the critical snarks. On the other hand, it is proven that non-hamiltonian K_{2}-hamiltonian graphs of any maximum degree exist. Several operations conserving K_{2}-hamiltonicity are described, one of which leads to the result that there exists an infinite family of non-hamiltonian K_{2}-hamiltonian graphs in which, asymptotically, a quarter of vertices has the property that removing such a vertex yields a non-hamiltonian graph. We extend a celebrated result of Tutte by showing that every planar K_{2}-hamiltonian graph with minimum degree at least 4 is hamiltonian. Finally, we investigate K_{2}-traceable graphs, and discuss open problems.
Remarks
Proposition 6 in Section 3.2 discusses the so-called dot product in the context of K_{2}-hamiltonicity. Unfortunately, the third and fourth paragraphs of its “proof” contain errors. Corrections have been added in Section 4 of the second paper in this series, see article № 57. A minor issue with Lemma 3 in Section 3.1 is also corrected.
Links
Full text as PDF
DOI: 10.1137/20M1355252
44. On 3-polytopes with non-hamiltonian prisms (with D. Ikegami and S. Maezawa)
J. Graph Theory 97, Iss. 4 (2021) 569–77.
Abstract
Špacapan recently showed that there exist 3-polytopes with non-hamiltonian prisms, disproving a conjecture of Rosenfeld and Barnette. By adapting Špacapan's approach we strengthen his result in several directions. We prove that there exists an infinite family of counterexamples to the Rosenfeld-Barnette conjecture, each member of which has maximum degree 37 and girth 4. We also show that for any given 3-polytope H there is a counterexample containing H as an induced subgraph. This yields an infinite family of non-hamiltonian 4-polytopes in which the proportion of quartic vertices tends to 1. However, Barnette's conjecture stating that every 4-polytope in which all vertices are quartic is hamiltonian still stands. Finally, we prove that the Grünbaum-Walther shortness coefficient of the family of all prisms of 3-polytopes is at most 59/60.
Links
Full text as PDF
DOI: 10.1002/jgt.22672
43. Non-hamiltonian graphs in which every edge-contracted subgraph is hamiltonian (with I. Fabrici, T. Madaras, M. Timková, and N. Van Cleemput)
Appl. Math. Comput. 392 (2021) Article 125714.
Abstract
A graph G is perihamiltonian if G itself is non-hamiltonian, yet every edge-contracted subgraph of G is hamiltonian. These graphs form a superclass of the hypohamiltonian graphs. By applying a recent result of Wiener on path-critical graphs, we prove the existence of infinitely many perihamiltonian graphs of connectivity k for any k ≥ 2. Furthermore, we show that every planar perihamiltonian graph of connectivity k contains a vertex of degree k. This strengthens the theorem of Thomassen stating that every planar hypohamiltonian graph contains a cubic vertex, and entails that if in a polyhedral graph of minimum degree at least 4 the set of vertices whose removal yields a non-hamiltonian graph is independent, the graph itself must be hamiltonian. Although it remains an open problem whether every planar hypohamiltonian graph contains adjacent cubic vertices, we here prove that there are infinitely many polyhedral perihamiltonian graphs for which this is not the case.
Links
Full text as PDF
Zbl 1462.05206
MR 4164893
DOI: 10.1016/j.amc.2020.125714
42. Spiders everywhere (with G. Wiener and M. Yokota)
Discrete Appl. Math. 289 (2021) 516–22.
Abstract
A
spider is a tree with at most one branch (a vertex of degree at least 3)
centred at the branch if it exists, and centred at any vertex otherwise. A graph
G is
arachnoid if for any vertex
v of
G, there exists a spanning spider of
G centred at
v—in other words: there are spiders everywhere!
Hypotraceable graphs are non-traceable graphs in which all vertex-deleted subgraphs are traceable. Gargano, Hammar, Hell, Stacho, and Vaccaro [
Discrete Math. 285 (2004) 83–95] defined arachnoid graphs as natural generalisations of traceable graphs and asked for the existence of arachnoid graphs that are (i) non-traceable and non-hypotraceable, or (ii) in which some vertex is the centre of only spiders with more than three legs. An affirmative answer to (ii) implies an affirmative answer to (i). While non-traceable, non-hypotraceable arachnoid graphs were described in [
J. Graph Theory 84 (2017) 443–59], (ii) remained open. In this paper we give an affirmative answer to this question and discuss spanning spiders whose legs must have some minimum length.
Links
Full text as PDF
Zbl 1454.05068
MR 4184344
DOI: 10.1016/j.dam.2020.11.017
41. Long Cycles and Spanning Subgraphs of Locally Maximal 1-planar Graphs (with I. Fabrici, J. Harant, T. Madaras, S. Mohr, and R. Soták)
J. Graph Theory 95, Iss. 1 (2020) 125–37.
Abstract
A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many 5-connected 1-planar non-traceable graphs are presented.
Links
arXiv:1912.08028
MR 4130388
DOI: 10.1002/jgt.22542
40. Non-hamiltonian 1-tough triangulations with disjoint separating triangles (with J. Fujisawa)
Discrete Appl. Math. 284 (2020) 622–5.
Abstract
In this note, we consider triangulations of the plane. Ozeki and the second author asked whether there are non-hamiltonian 1-tough triangulations in which every two separating triangles are disjoint. We answer this question in the affirmative and strengthen a result of Nishizeki by proving that there are infinitely many non-hamiltonian 1-tough triangulations with pairwise disjoint separating triangles.
Links
Full text as PDF
Zbl 1443.05108
MR 4115510
DOI: 10.1016/j.dam.2020.03.053
39. On minimum leaf spanning trees and a criticality notion (with K. Ozeki and G. Wiener)
Discrete Math. 343, Iss. 7 (2020) Article 111884.
Abstract
The minimum leaf number of a connected non-hamiltonian graph G is the number of leaves of a spanning tree of G with the fewest leaves among all spanning trees of G. Based on this quantity, Wiener introduced leaf-stable and leaf-critical graphs, concepts which generalise hypotraceability and hypohamiltonicity. In this article, we present new methods to construct leaf-stable and leaf-critical graphs and study their properties. Furthermore, we improve several bounds related to these families of graphs. These extend previous results of Horton, Thomassen, and Wiener.
Links
Full text as PDF
Zbl 1440.05062
MR 4076879
DOI: 10.1016/j.disc.2020.111884
38. Structural and computational results on platypus graphs (with J. Goedgebeur and A. Neyt)
Appl. Math. Comput. 386 (2020) Article 125491.
Abstract
A
platypus graph is a non-hamiltonian graph for which every vertex-deleted subgraph is traceable. They are closely related to families of graphs satisfying interesting conditions regarding longest paths and longest cycles, for instance hypohamiltonian, leaf-stable, and maximally non-hamiltonian graphs. In this paper, we first investigate cubic platypus graphs, covering all orders for which such graphs exist: in the general and polyhedral case as well as for snarks. We then present (not necessarily cubic) platypus graphs of girth up to 16—whereas no hypohamiltonian graphs of girth greater than 7 are known—and study their maximum degree, generalising two theorems of Chartrand, Gould, and Kapoor. Using computational methods, we determine the complete list of all non-isomorphic platypus graphs for various orders and girths. Finally, we address two questions raised by the third author in [
J. Graph Theory 86 (2017) 223–43].
Links
arXiv:1712.05158
Zbl 1462.05110
MR 4119967
DOI: 10.1016/j.amc.2020.125491
37. Shortness Coefficient of Cyclically 4-Edge-Connected Cubic Graphs (with O. S. Lo, J. M. Schmidt, and N. Van Cleemput)
Electron. J. Combin. 27, Iss. 1 (2020) Article Number P1.43.
Abstract
Grünbaum and Malkevitch proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most 76/77. Recently, this was improved to 359/366 (< 52/53) and the question was raised whether this can be strengthened to 41/42, a natural bound inferred from one of the Faulkner-Younger graphs. We prove that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most 37/38 and that we also get the same value for cyclically 4-edge-connected cubic graphs of genus g for any prescribed genus g ≥ 0. We also show that 45/46 is an upper bound for the shortness coefficient of cyclically 4-edge-connected cubic graphs of genus g with face lengths bounded above by some constant larger than 22 for any prescribed g ≥ 0.
Links
Full text as PDF
Zbl 1432.05059
MR 4064064
DOI: 10.37236/8440
36. Graphs with few Hamiltonian Cycles (with J. Goedgebeur and B. Meersman)
Math. Comp. 89 (2020) 965–91.
Abstract
We describe an algorithm for the exhaustive generation of non-isomorphic graphs with a given number k ≥ 0 of hamiltonian cycles, which is especially efficient for small k. Our main findings, combining applications of this algorithm and existing algorithms with new theoretical results, revolve around graphs containing exactly one hamiltonian cycle (1H) or exactly three hamiltonian cycles (3H). Motivated by a classic result of Smith and recent work of Royle, we show that there exist nearly cubic 1H graphs of order n iff n ≥ 18 is even. This gives the strongest form of a theorem of Entringer and Swart, and sheds light on a question of Fleischner originally settled by Seamone. We prove equivalent formulations of the conjecture of Bondy and Jackson that every planar 1H graph contains two vertices of degree 2, verify it up to order 16, and show that its toric analogue does not hold. We treat Thomassen's conjecture that every hamiltonian graph of minimum degree at least 3 contains an edge such that both its removal and its contraction yield hamiltonian graphs. We also verify up to order 21 the conjecture of Sheehan that there is no 4-regular 1H graph. Extending work of Schwenk, we describe all orders for which cubic 3H triangle-free graphs exist. We verify up to order 48 Cantoni's conjecture that every planar cubic 3H graph contains a triangle, and show that for every k that is 0 or at least 4 there exists a planar cyclically 4-edge-connected cubic graph with exactly k hamiltonian cycles. Finally, complementing work of Sheehan on 1H graphs of maximum size, we determine the maximum size of graphs containing exactly one hamiltonian path and give, for every order n, the exact number of such graphs on n vertices and of maximum size.
Links
arXiv:1812.05650
Zbl 1429.05114
MR 4044458
DOI: 10.1090/mcom/3465
35. On almost hypohamiltonian graphs (with J. Goedgebeur)
Discrete Math. Theoret. Comput. Sci. 21, No. 4 (2019) #5.
Abstract
A graph
G is
almost hypohamiltonian (a.h.) if
G is non-hamiltonian, there exists a vertex
w in
G such that
G − w is non-hamiltonian, and
G − v is hamiltonian for every vertex
v ≠ w in
G. The second author asked in [
J. Graph Theory 79 (2015) 63–81] for all orders for which a.h. graphs exist. Here we solve this problem. To this end, we present a specialised algorithm which generates complete sets of a.h. graphs for various orders. Furthermore, we show that the smallest cubic a.h. graphs have order 26. We provide a lower bound for the order of the smallest planar a.h. graph and improve the upper bound for the order of the smallest planar a.h. graph containing a cubic vertex. We also determine the smallest planar a.h. graphs of girth 5, both in the general and cubic case. Finally, we extend a result of Steffen on snarks and improve two bounds on longest paths and longest cycles in polyhedral graphs due to Jooyandeh, McKay, Östergård, Pettersson, and the second author.
Links
Full text as PDF
Zbl 1417.05114
MR 3995589
DOI: 10.23638/DMTCS-21-4-5
34. Polyhedra with few 3-cuts are hamiltonian (with G. Brinkmann)
Electron. J. Combin. 26, Iss. 1 (2019) Article Number P1.39.
Abstract
In 1956, Tutte showed that every planar 4-connected graph is hamiltonian. In this article, we will prove that even if we relax the prerequisites on the polyhedra from 4-connected to containing at most three 3-cuts, hamiltonicity is still guaranteed. This also strengthens a theorem of Jackson and Yu, who have shown the result for the subclass of triangulations. We also prove that polyhedra with at most four 3-cuts have a hamiltonian path. It is well known that for each k ≥ 6 non-hamiltonian polyhedra with k 3-cuts exist. We give computational results on lower bounds on the order of a possible non-hamiltonian polyhedron for the remaining open cases of polyhedra with four or five 3-cuts.
Links
Full text as PDF
Zbl 1409.05122
MR 3934370
DOI: 10.37236/7771
33. On a question of van Aardt et al. on destroying all longest cycles
Graphs Combin. 35, Iss. 2 (2019) 479–83.
Abstract
We describe an infinite family of 2-connected graphs, each of which has the property that the intersection of all longest cycles is empty. In particular, we present such graphs with circumference 10, 13, and 16. This settles a question of van Aardt et al. [
Discrete Appl. Math. 186 (2015) 251–9] concerning the existence of such graphs for all but one case, namely circumference 11. We also present a 2-connected graph of circumference 11 in which all but one vertex are avoided by some longest cycle.
Links
Full text as PDF
Zbl 1409.05119
MR 3914971
DOI: 10.1007/s00373-019-02010-9
32. Cubic vertices in planar hypohamiltonian graphs
J. Graph Theory 90, Iss. 2 (2019) 189–207.
Abstract
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.
Links
Full text as PDF
Zbl 07363267
MR 3891935
DOI: 10.1002/jgt.22388
31. On the size of maximally non-hamiltonian digraphs (with N. Lichiardopol)
Ars Math. Contemp. 16, No. 1 (2019) 59–66.
Abstract
A graph is called maximally non-hamiltonian if it is non-hamiltonian, yet for any two non-adjacent vertices there exists a hamiltonian path between them. In this paper, we naturally extend the concept to directed graphs and bound their size from below and above. Our results on the lower bound constitute our main contribution, while the upper bound can be obtained using a result of Lewin, but we give here a different proof. We describe digraphs attaining the upper bound, but whether our lower bound can be improved remains open.
Links
Full text as PDF
Zbl 1416.05166
MR 3904716
DOI: 10.26493/1855-3974.1291.ee9
30. Grinberg's Criterion (with G. Brinkmann)
Europ. J. Combin. 75 (2019) 32–42.
Abstract
We generalize Grinberg's hamiltonicity criterion for planar graphs. To this end, we first prove a technical theorem for embedded graphs. As a special case of a corollary of this theorem we obtain Zaks' extension of Grinberg's Criterion (which encompasses earlier work of Gehner and Shimamoto), but the result also implies Grinberg's formula in its original form in a much broader context. Further implications are a short proof for a slightly strengthened criterion of Lewis bounding the length of a shortest closed walk from below as well as a generalization of a theorem due to Bondy and Häggkvist.
Links
Full text as PDF
Zbl 1400.05138
MR 3862952
DOI: 10.1016/j.ejc.2018.07.017
29. Every 4-Connected Graph with Crossing Number 2 is Hamiltonian (with K. Ozeki)
SIAM J. Discrete Math. 32, No. 4 (2018) 2783–94.
Abstract
A seminal theorem of Tutte states that planar 4-connected graphs are hamiltonian. Applying a result of Thomas and Yu, one can show that every 4-connected graph with crossing number 1 is hamiltonian. In this paper, we continue along this path and prove the titular statement. We also discuss the traceability and hamiltonicity of 3-connected graphs with small crossing number and few 3-cuts, and present applications of our results.
Links
Full text as PDF
Zbl 1401.05175
MR 3882945
DOI: 10.1137/17M1138443
28. Regular non-hamiltonian polyhedral graphs (with N. Van Cleemput)
Appl. Math. Comput. 338 (2018) 192–206.
Abstract
Invoking Steinitz' Theorem, in the following a polyhedron shall be a planar 3-connected graph. From around 1880 till 1946 Tait's conjecture that cubic polyhedra are hamiltonian was thought to hold—its truth would have implied the Four Colour Theorem. However, Tutte gave a counterexample. We briefly survey the ensuing hunt for the smallest non-hamiltonian cubic polyhedron, the Lederberg-Bosák-Barnette graph, and prove that there exists a non-hamiltonian essentially 4-connected cubic polyhedron of order n if and only if n ≥ 42. This extends work of Aldred, Bau, Holton, and McKay. We then present our main results which revolve around the quartic case: combining a novel theoretical approach for determining non-hamiltonicity in (not necessarily planar) graphs of connectivity 3 with computational methods, we dramatically improve two bounds due to Zaks. In particular, we show that the smallest non-hamiltonian quartic polyhedron has at least 35 and at most 39 vertices, thereby almost reaching a quartic analogue of a famous result of Holton and McKay. As an application of our results, we obtain that the shortness coefficient of the family of all quartic polyhedra does not exceed 5/6. The paper ends with a discussion of the quintic case in which we tighten a result of Owens.
Remarks
The main finding of this paper was mentioned in the
September 2019 Feature Column of the American Mathematical Society, written by Joseph Malkevitch.
Links
Full text as PDF
Zbl 1427.05126
MR 3843691
DOI: 10.1016/j.amc.2018.05.062
27. Hamiltonian properties of polyhedra with few 3-cuts—A survey (with K. Ozeki and N. Van Cleemput)
Discrete Math. 341, Iss. 9 (2018) 2646–60.
Abstract
We give an overview of the most important techniques and results concerning the hamiltonian properties of planar 3-connected graphs with few 3-vertex-cuts. In this context, we also discuss planar triangulations and their decomposition trees. We observe an astonishing similarity between the hamiltonian behavior of planar triangulations and planar 3-connected graphs. In addition to surveying, (i) we give a unified approach to constructing non-traceable, non-hamiltonian, and non-hamiltonian-connected triangulations, and show that planar 3-connected graphs (ii) with at most one 3-vertex-cut are hamiltonian-connected, and (iii) with at most two 3-vertex-cuts are 1-hamiltonian, filling two gaps in the literature. Finally, we discuss open problems and conjectures.
Remarks
On page 2647, entry J of the caption of Table 1 should be: Brinkmann and Zamfirescu (2019) [12]
Links
Full text as PDF
Zbl 1392.05066
MR 3828776
DOI: 10.1016/j.disc.2018.06.015
26. Every graph occurs as an induced subgraph of some hypohamiltonian graph (with T. I. Zamfirescu)
J. Graph Theory 88, Iss. 4 (2018) 551–7.
Abstract
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_{3}, 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.
Links
Full text as PDF
Zbl 1393.05095
MR 3818596
DOI: 10.1002/jgt.22228
25. Gallai's question and constructions of almost hypotraceable graphs (with G. Wiener)
Discrete Appl. Math. 243 (2018) 270–8.
Abstract
Consider a graph G in which the longest path has order |V(G)| − 1. We denote the number of vertices v in G such that G − v is non-traceable with t_{G}. Gallai asked in 1966 whether, in a connected graph, the intersection of all longest paths is non-empty. Walther showed that, in general, this is not true. In a graph G in which the longest path has |V(G)| − 1 vertices, the answer to Gallai's question is positive iff t_{G} ≠ 0. In this article we study almost hypotraceable graphs, which constitute the extremal case t_{G} = 1. We give structural properties of these graphs, establish construction methods for connectivities 1 through 4, show that there exists a cubic 3-connected such graph of order 28, and draw connections to works of Thomassen and Gargano et al.
Remarks
On page 271 it is stated that “We follow Chen et al. [4], and call a vertex present in all longest paths of a given graph a Gallai vertex, and the set of all Gallai vertices the Gallai set.” Although our definition of a Gallai vertex is indeed equivalent to the definition given in the aforementioned paper by Chen et al., our definition of a Gallai set is not. This does not change the validity of any of the given statements.
Links
Full text as PDF
Zbl 1387.05072
MR 3804756
DOI: 10.1016/j.dam.2018.02.017
24. Non-hamiltonian triangulations with distant separating triangles (with K. Ozeki)
Discrete Math. 341, Iss. 7 (2018) 1900–2.
Abstract
In 1996 Böhme, Harant, and Tkáč asked whether there exists a non-hamiltonian triangulation with the property that any two of its separating triangles lie at distance at least 1. Two years later, Böhme and Harant answered this in the affirmative, showing that for any non-negative integer d there exists a non-hamiltonian triangulation with seven separating triangles every two of which lie at distance at least d. In this note we prove that the result holds if we replace seven with six, remarking that no non-hamiltonian triangulation with fewer than six separating triangles is known.
Links
Full text as PDF
Zbl 1387.05141
MR 3802143
DOI: 10.1016/j.disc.2018.03.018
23. Infinitely many planar cubic hypohamiltonian graphs of girth 5 (with J. Goedgebeur)
J. Graph Theory 88, Iss. 1 (2018) 40–5.
Abstract
A graph
G is
hypohamiltonian if
G is non-hamiltonian and for every vertex
v in
G, the graph
G − v 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.
Links
Full text as PDF
Zbl 1391.05153
MR 3781602
DOI: 10.1002/jgt.22183
22. Congruent triangles in arrangements of lines
Ars Math. Contemp. 14, No. 2 (2018) 359–73.
Abstract
We study the maximum number of congruent triangles in finite arrangements of ℓ lines in the Euclidean plane. Denote this number by f (ℓ). We show that f (5) = 5 and that the construction realizing this maximum is unique, f (6) = 8, and f (7) = 14. We also discuss for which integers c there exist arrangements on ℓ lines with exactly c congruent triangles. In parallel, we treat the case when the triangles are faces of the plane graph associated to the arrangement (i.e. the interior of the triangle has empty intersection with every line in the arrangement). Lastly, we formulate four conjectures.
Links
Full text as PDF
Zbl 1396.52022
MR 3812026
DOI: 10.26493/1855-3974.982.6d6
21. On hypohamiltonian snarks and a theorem of Fiorini (with J. Goedgebeur)
Ars Math. Contemp. 14, No. 2 (2018) 227–49.
Abstract
We discuss an omission in the statement and proof of Fiorini's 1983 theorem on
hypohamiltonian snarks and present a version of this theorem which is more general in several ways.
Using Fiorini’s erroneous result, Steffen showed that hypohamiltonian snarks exist for some n ≥ 10 and
each even n ≥ 92. We rectify Steffen's proof by providing a correct demonstration of a technical lemma on
flower snarks, which might be of separate interest. We then strengthen Steffen's theorem to the strongest possible
form by determining all orders for which hypohamiltonian snarks exists. This also strengthens a result of Máčajová and Škoviera. Finally, we verify a conjecture of Steffen on hypohamiltonian snarks up to 36 vertices.
Links
Full text as PDF
Zbl 1395.05044
MR 3812019
DOI: 10.26493/1855-3974.1176.9b7
20. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable
J. Graph Theory 86, Iss. 2 (2017) 223–43.
Abstract
We call a graph G a platypus if G is non-hamiltonian, and for any vertex v in G, the graph G − v is traceable. Every hypohamiltonian and every hypotraceable graph is a platypus, but there exist platypuses which 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 k ≥ 2.
Remarks
Reference 11 from the journal version will not appear in Ars Math. Contemp. as indicated there—this is a misprint. Reference 11 has been split into articles № 23 and № 35, see above. In the proof of Theorem 2.3, “v ∈ V(S)” should be v ∈ S.
Links
Full text as PDF
Zbl 1370.05115
MR 3684784
DOI: 10.1002/jgt.22122
19. Improved bounds for hypohamiltonian graphs (with J. Goedgebeur)
Ars Math. Contemp. 13, No. 2 (2017) 235–57.
Abstract
A graph G is hypohamiltonian if G is non-hamiltonian and G − v is hamiltonian for every v ∈ V(G). In the following, every graph is assumed to be hypohamiltonian. Aldred, Wormald, and McKay gave a list of all graphs of order at most 17. In this article, we present an algorithm to generate all graphs of a given order and apply it to prove that there exist exactly 14 graphs of order 18 and 34 graphs of order 19. We also extend their results in the cubic case. Furthermore, we show that (i) the smallest graph of girth 6 has order 25, (ii) the smallest planar graph has order at least 23, (iii) the smallest cubic planar graph has order at least 54, and (iv) the smallest cubic planar graph of girth 5 with non-trivial automorphism group has order 78.
Links
Full text as PDF
Zbl 1380.05034
MR 3720529
DOI: 10.26493/1855-3974.1044.eaa
18. Planar Hypohamiltonian Graphs on 40 Vertices (with M. Jooyandeh, B. D. McKay, P. R. J. Östergård, and V. H. Pettersson)
J. Graph Theory 84, Iss. 2 (2017) 121–33.
Abstract
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 hypohamiltonian planar graph of girth 5 has 45 vertices.
Links
Full text as PDF
Zbl 1356.05029
MR 3601121
DOI: 10.1002/jgt.22015
17. A cut locus for finite graphs and the farthest point mapping (with A. Maddaloni)
Discrete Math. 339, Iss. 1 (2016) 354–64.
Abstract
We reflect upon an analogue of the cut locus, a notion classically studied in Differential Geometry, for finite graphs. The cut locus C(x) of a vertex x shall be the graph induced by the set of all vertices y with the property that no shortest path between x and z, z ≠ y, contains y. The cut locus coincides with the graph induced by the vertices realizing the local maxima of the distance function. The function F mapping a vertex x to F(x), the set of global maxima of the distance function from x, is the farthest point mapping. Among other things, we observe that if for a vertex x, C(x) is connected, then C(x) is the graph induced by F(x), and prove that the farthest point mapping has period 2. Elaborating on the analogy with Geometry, we study graphs satisfying Steinhaus' condition, i.e. graphs for which the farthest point mapping is single-valued and involutive.
Links
Full text as PDF
Zbl 1322.05048
MR 3404497
DOI: 10.1016/j.disc.2015.08.003
16. Dissecting the square into five congruent parts (with L. Yuan and T. I. Zamfirescu)
Discrete Math. 339, Iss. 1 (2016) 288–98.
Abstract
We give an affirmative answer to an old conjecture proposed by Ludwig Danzer: there is a unique
dissection of the square into five congruent convex tiles.
Remarks
This paper was mentioned in
an article on Martin Gardner's work, written by Colm Mulcahy for his Guest Blog in the Scientific American.
Links
Full text as PDF
Zbl 1322.05038
MR 3404490
DOI: 10.1016/j.disc.2015.08.009
15. On Hypohamiltonian and Almost Hypohamiltonian Graphs
J. Graph Theory 79, Iss. 1 (2015) 63–81.
Abstract
A graph G is almost hypohamiltonian if G is non-hamiltonian, there exists a vertex w such that G − w is non-hamiltonian, and for any vertex v ≠ w the graph G − v 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 n ≥ 74. 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.
Remarks
The PDF available here contains corrections with respect to the published version.
For details, see the last page of the PDF.
Links
Full text as PDF
Zbl 1312.05076
MR 3322695
DOI: 10.1002/jgt.21815
14. Small k-pyramids and the complexity of determining k (with B. Schauerte)
J. Discrete Algorithms 30 (2015) 13–20.
Abstract
Motivated by the computational complexity of determining whether a graph is hamiltonian, we study under algorithmic aspects a class of polyhedra called
k-pyramids, introduced in [
C. T. Zamfirescu and T. I. Zamfirescu, Math. Nachr. 284 (2011) 1739–47], and discuss related applications. We prove that determining whether a given graph is the 1-skeleton of a
k-pyramid, and if so whether it is belted or not, can be done in polynomial time for
k ≤ 3. The impact on hamiltonicity follows from the traceability of all 2-pyramids and non-belted 3-pyramids, and from the hamiltonicity of all non-belted 2-pyramids. The algorithm can also be used to determine the outcome for larger values of
k, but the complexity increases with
k. Lastly, we present applications of the algorithm, and improve the known bounds for the minimal cardinality of systems of bases called foundations in graph families with interesting properties concerning traceability and hamiltonicity.
Links
Full text as PDF
Zbl 06403388
MR 3305147
DOI: 10.1016/j.jda.2014.11.003
13. Lattice graphs with non-concurrent longest cycles (with A. Dino Jumani and T. I. Zamfirescu)
Rend. Sem. Mat. Univ. Padova 132 (2014) 75–82.
Abstract
No hypohamiltonian graphs are embeddable in the planar square lattice L². The lattice L² contains, however, graphs in which every vertex is missed by some longest cycle. In this paper we present graphs with this property, embeddable in various lattices, and of considerably smaller order than those previously known.
Links
Full text as PDF
Zbl 1306.05114
MR 3276827
DOI: 10.4171/RSMUP/132-6
12. Improved bounds for acute triangulations of convex polygons
Util. Math. 91 (2013) 71–9.
Abstract
Links
Full text as PDF
Zbl 1292.52003
MR 3097891
11. Balanced triangulations (with L. Jia, L. Yuan, and T. I. Zamfirescu)
Discrete Math. 313, Iss. 20 (2013) 2178–91.
Abstract
Motivated by applications in numerical analysis, we investigate balanced triangulations, i.e. triangulations where all angles are strictly larger than π/6 and strictly smaller than π/2, giving the optimal lower bound for the number of triangles in the case of the square. We also investigate platonic surfaces, where we find for each one its respective optimal bound. In particular, we settle (affirmatively) the open question whether there exist acute triangulations of the regular dodecahedral surface with 12 acute triangles
[
J. Itoh and T. Zamfirescu, Eur. J. Combin. 28 (2007) 1072–86].
Links
Full text as PDF
Zbl 1285.52004
MR 3084261
DOI: 10.1016/j.disc.2013.05.017
10. Intersecting longest paths and longest cycles: A survey (with A. Shabbir and T. I. Zamfirescu)
Electron. J. Graph Theory Appl. 1, No. 1 (2013) 56–76.
Abstract
This is a survey of results obtained during the last 45 years regarding the intersection behaviour of all longest paths, or all longest cycles, in connected graphs. Planar graphs and graphs of higher connectivity receive special attention. Graphs embeddable in the cubic lattice of arbitrary dimension, and graphs embeddable in the triangular or hexagonal lattice of the plane are also discussed. Results concerning the case when not all, but just some longest paths or cycles are intersected, for example two or three of them, are also reported.
Links
Full text as PDF
Zbl 1306.05121
MR 3093252
DOI: 10.5614/ejgta.2013.1.1.6
09. (2)-pancyclic graphs
Discrete Appl. Math. 161, Iss. 7–8 (2013) 1128–36.
Abstract
We introduce the class of (2)-pancyclic graphs, which are simple undirected finite connected graphs
of order n having exactly two cycles of length p for each p satisfying 3 ≤ p ≤ n, analyze their properties,
and give several examples of such graphs, among which are the smallest.
Remarks
For corrections with respect to the published version, please see: errata.
Links
Full text as PDF
Zbl 1262.05090
MR 3030597
DOI: 10.1016/j.dam.2012.11.002
08. Survey of two-dimensional acute triangulations
Discrete Math. 313, Iss. 1 (2013) 35–49.
Abstract
We give a brief introduction to the topic of two-dimensional acute triangulations, mention results on
related areas, survey existing achievements—with emphasis on recent activity—and list related open
problems, both concrete and conceptual.
Links
Full text as PDF
Zbl 1261.52012
MR 3016971
DOI: 10.1016/j.disc.2012.09.016
07. Hypohamiltonian graphs and their crossing number
Electron. J. Combin. 19, Iss. 4 (2012) Article Number P12.
Abstract
We prove that for every k ≥ 0 there is an n_{0}(k) such that, for every n ≥ n_{0}, there exists a hypohamiltonian graph which has order n and crossing number k.
Remarks
For corrections with respect to the published version (which coincides with the PDF below), please see: errata.
Links
Full text as PDF
Zbl 1266.05079
MR 3001649
DOI: 10.37236/2291
06. Hamiltonian properties of generalized pyramids (with T. I. Zamfirescu)
Math. Nachr. 281, Iss. 13 (2011) 1739–47.
Abstract
We investigate here the hamiltonicity of a class of polytopes generalizing pyramids, prisms, and polytopes with Halin 1-skeleta.
Links
Full text as PDF
Zbl 1236.05121
MR 2832679
DOI: 10.1002/mana.200910058
05. An infinite family of planar non-hamiltonian bihomogeneously traceable oriented graphs
Graphs Combin. 26, Iss. 1 (2010) 141–6.
Abstract
We answer an open question on planar non-hamiltonian bihomogeneously traceable digraphs without opposite arcs by constructing an infinite family of such graphs.
Links
Full text as PDF
Zbl 1231.05163
MR 2606625
DOI: 10.1007/s00373-010-0900-6
04. Acute triangulations of doubly covered convex quadrilaterals (with L. Yuan)
Boll. Unione Mat. Ital., Sez. B, Artic. Ric. Mat. (8) 10, Iss. 3 (2007) 933–8.
Abstract
Motivated by various applications triangulations of surfaces using only acute triangles have been recently studied. Triangles and quadrilaterals can be triangulated with at most 7, respectively 10, acute triangles. Doubly covered triangles can be triangulated with at most 12 acute triangles. In this paper we investigate the acute triangulations of doubly covered convex quadrilaterals, and show that they can be triangulated with at most 20 acute triangles.
Links
Full text as PDF
Zbl 1185.52018
MR 2507906
03. A planar hypohamiltonian graph with 48 vertices (with T. I. Zamfirescu)
J. Graph Theory 55, Iss. 4 (2007) 338–42.
Abstract
We present a planar hypohamiltonian graph on 48 vertices, and derive some consequences.
Remarks
Fig. 8 is incorrect: erratum.
Links
Full text as PDF
Zbl 1120.05054
MR 2336805
DOI: 10.1002/jgt.20241
02. Regular graphs in which every pair of points is missed by some longest cycle (with B. Schauerte)
An. Univ. Craiova, Ser. Mat. Inf. 33 (2006) 154–73.
Abstract
In Petersen's well-known cubic graph every vertex is missed by some longest cycle. Thomassen produced a planar graph with this property. Grünbaum found a cubic graph, in which any two vertices are missed by some longest cycle. In this paper we present a cubic planar graph fulfilling this condition.
Remarks
On page 156, line 1, the cycle should be: a_1a_2a'_2a'_3a_3a_4a'_4a'_5a'_1a_1.
Links
Full text as PDF
Zbl 1174.05419
MR 2359901
Journal Link
01. Acute triangulations of the double triangle
Bull. Math. Soc. Sci. Math. Roumanie 47 (95), Iss. 3–4 (2004) 189–93.
Abstract
We prove that every doubly covered triangle can be triangulated with 12 acute triangles, and this number is best possible.
Links
Full text as PDF
Zbl 1114.52012
MR 2121985
Journal Link