Cubic maximal nontraceable graphs

2004/07/16 by Marietjie Frick, Frick, Marietjie, Joy Singleton +1
Computer Science · Mathematics · #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C38

paper · pdf · doi:10.48550/arxiv.math/0407290

9 pages, 6 figures

arxiv created 2004/07/16 · openalex publication_date 2004/07/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We determine a lower bound for the number of edges of a 2-connected maximal nontraceable graph, and present a construction of an infinite family of maximal nontraceable graphs that realize this bound.

Related

• Lower bound for the size of maximal nontraceable graphs
• An Upper Bound of 7n/6 for the Minimum Size 2EC on Cubic 3-Edge Connected Graphs
• Hoffmann-Ostenhof's conjecture for traceable cubic graphs
• Maximum edges possible in a graph for restricted independence number, maximum degree, and maximum matching size
• The maximum size of a nonhamiltonian graph with given order and connectivity