Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Extremal problems ab ...
Article

Extremal problems about the order and size of nonhamiltonian locally linear graphs

Feng Liu (1), Leilei Zhang ORCID (2)
(1) Shanghai Jiao Tong University [SJTU]
(2) Central China Normal University [CCNU]
Download article
Open on arXiv
Submitted on
April 16, 2026
Accepted on
September 12, 2026
Published on
September 16, 2026
Last modified on
September 16, 2026
Volume 28
vol. 28:3
Graph Theory
DOI
10.46298/dmtcs.18029
Indicators
61
Views
21
Downloads

Extremal problems about the order and size of nonhamiltonian locally linear graphs

Feng Liu (1), Leilei Zhang ORCID (2)
(1) Shanghai Jiao Tong University [SJTU]
(2) Central China Normal University [CCNU]
Abstract
The relation between local structure and global cycle properties is a classical topic in graph theory. A graph $G$ is locally linear if $G[N(v)]$ is a path for every $v\in V(G)$. It is locally Hamiltonian or locally traceable if every vertex neighborhood induces a Hamiltonian or traceable graph, respectively. Earlier work by Pareek and Skupień, Skupień, Davies and Thomassen, Asratian and Oksimets, and de Wet and van Aardt studied extremal questions for these related graph classes. We prove that the minimum order of a nonhamiltonian locally linear graph is $12$ and that, for every integer $n\geq 12$, the minimum size of such a graph of order $n$ is $2n$. We also prove that every nontraceable locally linear graph of order $n$ has at least $2n+3$ edges. 16 pages, 4 figures
Keywords
  • Combinatorics
  • 05C35, 05C45, 05C69
Preview
Loading PDF preview...
References

  1. A. S. Asratian and N. Oksimets. Graphs with Hamiltonian Balls. Australas. J. Combin., 17:185-198, 1998.

  2. J. A. Bondy and U. S. R. Murty. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008. xii+651 pp.

  3. V. Chernyshev, J. Rauch, and D. Rautenbach. Forest cuts in sparse graphs. Discrete Math., 348(11):Paper No. 114594, 2025.

    DOI : 10.1016/j.disc.2025.114594

  4. B. L. Chilton, R. Gould, and A. D. Polimeni. A note on graphs whose neighborhoods are n-cycles. Geom. Dedicata, 3:289-294, 1974.

    DOI : 10.1007/bf00181321

  5. J. Davies and C. Thomassen. Locally Hamiltonian graphs and minimal size of maximal graphs on a surface. Electron. J. Combin., 27:Paper No. 2.25, 2020.

    DOI : 10.37236/9286

  6. J. P. de Wet and S. A. van Aardt. Traceability of locally Hamiltonian and locally traceable graphs. Discrete Math. Theor. Comput. Sci., 17(3):245-262, 2016.

    DOI : 10.46298/dmtcs.2144

  7. J. P. de Wet, M. Frick, and S. A. van Aardt. Hamiltonicity of locally Hamiltonian and locally traceable graphs. Discrete Appl. Math., 236:137-152, 2018.

    DOI : 10.1016/j.dam.2017.10.030

  8. A. L. Gavrilyuk and A. A. Makhnev. Terwilliger graphs in which the neighborhood of some vertex is isomorphic to a Petersen graph. Dokl. Math., 78:550-553, 2008.

    DOI : 10.1134/s1064562408040212

  9. A. L. Gavrilyuk, A. A. Makhnev, and D. V. Paduchikh. On graphs in which the neighborhood of each vertex is isomorphic to the Gewirtz graph. Dokl. Math., 80:684-688, 2009.

    DOI : 10.1134/s1064562409050147

  10. M. L. Kardanova, A. A. Makhnev, and D. V. Paduchikh. On graphs in which the neighborhood of each vertex is isomorphic to the Higman-Sims graph. Dokl. Math., 84:471-474, 2011.

    DOI : 10.1134/s1064562411040119

  11. R. C. Laskar and H. M. Mulder. Path-neighborhood graphs. Discuss. Math. Graph Theory, 33:731-745, 2013.

    DOI : 10.7151/dmgt.1700

  12. R. C. Laskar, H. M. Mulder, and B. Novick. Maximal outerplanar graphs as chordal graphs, path- neighborhood graphs, and triangle graphs. Australas. J. Combin., 52:185-195, 2012.

  13. C. L. Li, Y. R. Tang, and X. Zhan. The minimum size of a k-connected locally nonforesty graph, 2025. arXiv:2501.13980.

  14. J. W. Moon. On extremal graphs containing no wheels. Acta Math. Acad. Sci. Hungar., 16:13-18, 1965.

    DOI : 10.1007/bf01886385

  15. C. M. Pareek. On the maximum degree of locally Hamiltonian nonhamiltonian graphs. Utilitas Math., 23:103-120, 1983.

    DOI : 10.1016/s0167-5060(08)70079-7

  16. C. M. Pareek and Z. Skupień. On the smallest nonhamiltonian locally Hamiltonian graph. J. Univ. Kuwait (Sci.), 10:9-17, 1983.

  17. T. D. Parsons and T. Pisanski. Graphs which are locally paths. In Combinatorics and Graph Theory, volume 25 of Banach Center Publ., pages 127-135. PWN, Warsaw, 1989.

  18. Z. Skupień. Locally Hamiltonian graphs and Kuratowski's theorem. Bull. Acad. Pol. Sci. Sér. Sci. Math. Astron. Phys., 13:615-619, 1965.

  19. Z. Skupień. Locally Hamiltonian and planar graphs. Fund. Math., 58:193-200, 1966.

  20. L. Tang and E. Vumar. A Note on Cycles in Locally Hamiltonian and Locally Hamilton-Connected Graphs. Discussiones Mathematicae Graph Theory, 40:77-84, 2020.

    DOI : 10.7151/dmgt.2124

  21. S. A. van Aardt, M. Frick, O. Oellermann, and J. P. de Wet. Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs. Discrete Appl. Math., 205:171-179, 2016.

    DOI : 10.1016/j.dam.2015.09.022

  22. Y. Wang and X. Yang. Local properties of graphs that induce global cycle properties. Opuscula Math., 45:275-285, 2025.

    DOI : 10.7494/opmath.2025.45.2.275

  23. H. Yu and B. Wu. Graphs in which G -N [v] is a cycle for each vertex v. Discrete Math., 344:112519, 2021.

    DOI : 10.1016/j.disc.2021.112519