An official website of the United States government
ABSTRACT In 1973, Chvátal conjectured that there exists a constant such that every ‐tough graph on at least three vertices is Hamiltonian. This conjecture has inspired extensive research and has been verified for several special classes of graphs. Notably, Jung in 1978 proved that every 1‐tough ‐free graph on at least three vertices is Hamiltonian. However, the problem remains challenging even when restricted to graphs with no induced , the disjoint union of a path on four vertices and a one‐vertex path. In 2013, Nikoghosyan conjectured that every 1‐tough ‐free graph on at least three vertices is Hamiltonian. Later in 2015, Broersma remarked that “this question seems to be very hard to answer, even if we impose a higher toughness.” Instead he posed the following question: “Is the general conjecture of Chvátal's true for ‐free graphs?” We provide a positive answer to Broersma's question by establishing that every 23‐tough ‐free graph on at least three vertices is Hamiltonian.
more »
« less
Longest cycles in vertex‐transitive and highly connected graphs
Abstract We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively, states that all connected vertex‐transitive graphs contain a Hamiltonian path, and that all sufficiently large such graphs even contain a Hamiltonian cycle. The third conjecture, due to Smith from 1984, states that for in every ‐connected graph any two longest cycles intersect in at least vertices. In this paper, we prove a new lemma about the intersection of longest cycles in a graph, which can be used to improve the best known bounds toward all the aforementioned conjectures: First, we show that every connected vertex‐transitive graph on vertices contains a cycle (and hence path) of length at least , improving on from DeVos [arXiv:2302:04255, 2023]. Second, we show that in every ‐connected graph with , any two longest cycles meet in at least vertices, improving on from Chen, Faudree, and Gould [J. Combin. Theory, Ser. B,72(1998) no. 1, 143–149]. Our proof combines combinatorial arguments, computer search, and linear programming.
more »
« less
- Award ID(s):
- 2247013
- PAR ID:
- 10633691
- Publisher / Repository:
- NA
- Date Published:
- Journal Name:
- Bulletin of the London Mathematical Society
- ISSN:
- 0024-6093
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
ABSTRACT The famous Dirac's theorem states that for each every ‐vertex graph with minimum degree has a Hamiltonian cycle. When , this cannot be guaranteed, but the existence of some other specific subgraphs can be provided. Gargano, Hammar, Hell, Stacho, and Vaccaro proved that every connected ‐vertex graph with contains a spanningspider, that is, a spanning tree with at most one vertex of degree at least 3. Later, Chen, Ferrara, Hu, Jacobson, and Liu proved the stronger (and exact) result that for every connected ‐vertex graph with contains a spanningbroom, that is, a spanning spider obtained by joining the center of a star to an endpoint of a path. They also showed that a 2‐connected graph with and some additional properties contains a spanningjellyfish, which is a graph obtained by gluing the center of a star to a vertex in a cycle disjoint from that star. Note that every spanning jellyfish contains a spanning broom. The goal of this paper is to prove an exact Ore‐type bound which guarantees the existence of a spanning jellyfish: We prove that if is a 2‐connected graph on vertices such that every nonadjacent pair of vertices satisfies , then has a spanning jellyfish. As corollaries, we obtain strengthenings of two results by Chen et al.: a minimum degree condition guaranteeing the existence of a spanning jellyfish, and an Ore‐type sufficient condition for the existence of a spanning broom. The corollaries are sharp for infinitely many . One of the main ingredients of our proof is a modification of the Hopping Lemma due to Woodall.more » « less
-
A graph is said to be edge-transitive if its automorphism group acts transitively on its edges. It is known that edge-transitive graphs are either vertex-transitive or bipartite. We present a complete classification of all connected edge-transitive graphs on less than or equal to 20 vertices. We investigate biregular bipartite edge-transitive graphs and present connections to combinatorial designs, and we show that the Cartesian products of complements of complete graphs give an additional family of edge-transitive graphs.more » « less
-
The transitive closure of a graph is a new graph where every vertex is directly connected to all vertices to which it had a path in the original graph. Transitive closures are useful for reachability and relationship querying. Finding the transitive closure can be computationally expensive and requires a large memory footprint as the output is typically larger than the input. Some of the original research on transitive closures assumed that graphs were dense and used dense adjacency matrices. We have since learned that many real-world networks are extremely sparse, and the existing methods do not scale. In this work, we introduce a new algorithm called Anti-section Transitive Closure (ATC) for finding the transitive closure of a graph. We present a new parallel edges operation – anti-sections – for finding new edges to reachable vertices. ATC scales to massively multithreaded systems such as NVIDIA’s GPU with tens of thousands of threads. We show that the anti-section operation shares some traits with the triangle counting intersection operation in graph analysis. Lastly, we view the transitive closure problem as a dynamic graph problem requiring edge insertions. By doing this, our memory footprint is smaller. We also show a method for creating the batches in parallel using two different techniques: dual-round and hash. Using these techniques and the Hornet dynamic graph data structure, we show our new algorithm on an NVIDIA Titan V GPU. We compare with other packages such as NetworkX, SEI-GBTL, SuiteSparse, and cuSparse.more » « less
-
ABSTRACT In 1956, Tutte proved the celebrated theorem that every 4‐connected planar graph is Hamiltonian. This result implies that every more than ‐tough planar graph on at least three vertices is Hamiltonian and so has a 2‐factor. Owens in 1999 constructed non‐Hamiltonian maximal planar graphs of toughness arbitrarily close to and asked whether there exists a maximal non‐Hamiltonian planar graph of toughness exactly . In fact, the graphs Owens constructed do not even contain a 2‐factor. Thus the toughness of exactly is the only case left in asking the existence of 2‐factors in tough planar graphs. This question was also asked by Bauer, Broersma, and Schmeichel in a survey. In this paper, we close this gap by constructing a maximal ‐tough plane graph with no 2‐factor, answering the question asked by Owens as well as by Bauer, Broersma, and Schmeichel.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1112/blms.70134
