The minimality of the Georges--Kelmans graph Brinkmann, Gunnar; Goedgebeur, Jan; McKay, Brendan
Mathematics of computation,
May 1, 2022, Letnik:
91, Številka:
335
Journal Article
Recenzirano
In 1971, Tutte wrote in an article that it is tempting to conjecture that every 3-connected bipartite cubic graph is hamiltonian . Motivated by this remark, Horton constructed a counterexample on 96 ...vertices. In a sequence of articles by different authors several smaller counterexamples were presented. The smallest of these graphs is a graph on 50 vertices which was discovered independently by Georges and Kelmans. In this article we show that there is no smaller counterexample. As all non-hamiltonian 3-connected bipartite cubic graphs in the literature have cyclic 4-cuts—even if they have girth 6—it is natural to ask whether this is a necessary prerequisite. In this article we answer this question in the negative and give a construction of an infinite family of non-hamiltonian cyclically 5-connected bipartite cubic graphs.
In 1969 Barnette gave a weaker version of the conjecture stating that 3-connected planar bipartite cubic graphs are hamiltonian. We show that Barnette’s conjecture is true up to at least 90 vertices. We also report that a search of small non-hamiltonian 3-connected bipartite cubic graphs did not find any with genus less than 4.
We present a new subclass of interval graphs that generalizes connected proper interval graphs. These graphs are characterized by vertex orderings called connected perfect elimination orderings ...(PEO), i.e., PEOs where consecutive vertices are adjacent. Alternatively, these graphs can also be characterized by special interval models and clique orderings. We present a linear-time recognition algorithm that uses PQ-trees. Furthermore, we study the behavior of multi-sweep graph searches on this graph class. This study also shows that Corneil’s well-known LBFS-recognition algorithm for proper interval graphs can be generalized to a large family of graph searches. Finally, we show that a strong result on the existence of Hamiltonian paths and cycles in proper interval graphs can be generalized to semi-proper interval graphs.
•Introduction of semi-proper interval graphs, a novel subclass of interval graphs generalizing connected proper interval graphs.•Linear-time recognition algorithm for semi-proper interval graphs.•Generalization of Corneil’s LBFS recognition algorithm of proper interval graphs.•Generalization of Hamilton properties of proper interval graphs to semi-proper intervals.
System-level fault diagnosis model, namely, the PMC model, detects fault nodes only through the mutual testing of nodes in the system without physical equipment. In order to achieve server nodes ...fault diagnosis in large-scale data center networks (DCNs), the traditional algorithm based on the PMC model cannot meet the characteristics of high diagnosability, high accuracy and high efficiency due to its inability to ensure that the test nodes are fault-free. This paper first proposed a fault-tolerant Hamiltonian cycle fault diagnosis (FHFD) algorithm, which tests nodes in the order of the Hamiltonian cycle to ensure that the test nodes are faultless. In order to improve testing efficiency, a hierarchical diagnosis mechanism was further proposed, which recursively divides high scale structures into a large number of low scale structures based on the recursive structure characteristics of DCNs. Additionally, we proved that $ 2(n-2){n^{k-1}} $ and $ (n-2){t_{n, k}}/{t_{n, 1}} $ faulty nodes could be detected for $ BCub{e_{n, k}} $ and $ DCel{l_{n, k}} $ within a limited time for the proposed diagnosis strategy. Simulation experiments have also shown that our proposed strategy has improved the diagnosability and test efficiency dramatically.
We study how few longest cycles a regular graph can have under additional constraints. For each integer r≥5, we give exponential improvements for the best asymptotic upper bounds for this invariant ...under the additional constraint that the graphs are r-regular hamiltonian graphs. Earlier work showed that a conjecture by Haythorpe (2018) on a lower bound for this invariant is false because of an incorrect constant factor, whereas our results imply that the conjecture is even asymptotically incorrect. Motivated by a question of Zamfirescu (2022) and work of Chia and Thomassen (2012), we also study this invariant for non-hamiltonian 2-connected r-regular graphs and show that in this case the invariant can be bounded from above by a constant for all large enough graphs, even for graphs with arbitrarily large girth.
Recently, the problem of counting Hamiltonian cycles in 2-tiled graphs was resolved by Vegi Kalamar, Bokal, and Žerak. In this paper, we continue our research on generalized tiled graphs. We extend ...algorithms on counting traversing Hamiltonian cycles from 2-tiled graphs to generalized tiled graphs. We further show that, similarly as for 2-tiled graphs, for a fixed finite set of tiles, counting traversing Hamiltonian cycles can be performed in linear time with respect to the size of such graph, implying that counting traversing Hamiltonian cycles in tiled graphs is fixed-parameter tractable.
For a 2-connected graph G, the relative length of G, denoted by diff(G), is the difference between the orders of a longest path and a longest cycle in G. This parameter is used as a measure to ...estimate how close a given graph is to a hamiltonian graph. Let σk(G) be the least value of the sums of degrees of vertices in independent sets of cardinality k. In 2008, Paulusma and Yoshimoto proved that a 2-connected triangle-free graph G of order n with σ4(G)≥n+2 satisfies diff(G)≤1 unless G is isomorphic to one exceptional graph G0. In this paper, we extend their result and prove that for an integer s with 23(n+4)<s≤n+2, a 2-connected triangle-free graph of order n with σ4(G)≥s satisfies diff(G)≤n+3−s unless s=σ4(G)=n+2 and G=G0.
We present an algorithm which can generate all pairwise non-isomorphic K2-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 specifically designed for K2-hypohamiltonian graphs, allowing us to improve upon earlier computational results. Specifically, we characterise the orders for which K2-hypohamiltonian graphs exist and improve existing lower bounds on the orders of the smallest planar and the smallest bipartite K2-hypohamiltonian graphs. Furthermore, we describe a new operation for creating K2-hypohamiltonian graphs that preserves planarity under certain conditions and use it to prove the existence of a planar K2-hypohamiltonian graph of order n for every integer n≥134. Additionally, motivated by a theorem of Thomassen on hypohamiltonian graphs, we show the existence K2-hypohamiltonian graphs with large maximum degree and size.
Let n⩾k⩾1 be integers and define n={1,…,n}. For a set A let A(k) be the set of all k-element subsets of A. The Kneser graph K(n,k) is the graph with vertex set V=n(k) and edge set ...E={{x,y}∈V(2):x∩y=∅}. Chen proved that for n⩾3k, Kneser graphs are Hamiltonian and later improved this to n⩾2.62k+1. Furthermore, Chen and Füredi gave a short proof that if k|n, Kneser graphs are Hamiltonian for n⩾3k. In this note, we present a short proof that does not need the divisibility condition, i.e., we give a short proof that K(n,k) is Hamiltonian for n⩾4k.
For integers k≥3 and 1≤ℓ≤k−1, we prove that for any α>0, there exist ϵ>0 and C>0 such that for sufficiently large n∈(k−ℓ)N, the union of a k-uniform hypergraph with minimum vertex degree αnk−1 and a ...binomial random k-uniform hypergraph G(k)(n,p) with p≥n−(k−ℓ)−ϵ for ℓ≥2 and p≥Cn−(k−1) for ℓ=1 on the same vertex set contains a Hamiltonian ℓ-cycle with high probability. Our result is best possible up to the values of ϵ and C and answers a question of Krivelevich, Kwan and Sudakov.
PDF
