Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Saito’s Conjecture and the Oberly–Sumner Conjectures

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

For a given graph property \(\mathcal {P}\), we say a graph G is locally \(\mathcal {P}\) if for each \(v \in V(G)\), the subgraph induced by the open neighbourhood of v has property \(\mathcal P\). A closed locally \(\mathcal {P}\) graph is defined analogously in terms of closed neighbourhoods. It is known that connected locally hamiltonian graphs are not necessarily hamiltonian. Saito (in Computational Geometry and Graph Theory, Lecture Notes in Computer Science, vol. 4535, pp. 191–200. Springer, Berlin, 2008) conjectured that if G is a graph of order at least 3 such that for every vertex v in G the subgraph induced by the closed neighbourhood N[v] of v satisfies the Chvátal–Erdős condition for hamiltonicity, then G is hamiltonian. Oberly and Sumner (in J Graph Theory 3:351–356, 1979) conjectured that if G is a connected, locally k-connected \(K_{1,k+2}\)-free graph of order at at least 3, then G is hamiltonian. We prove a result that lends support to both these conjectures. We also provide a framework for investigating these and other related conjectures.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Asratian, A.: Some properties of graphs with local Ore condition. ARS Comb. 41, 97–106 (1995)

    MathSciNet  MATH  Google Scholar 

  2. Bertossi, A.A.: The edge hamiltonian path problem is NP-complete. Inf. Process. Lett. 13, 157–159 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bondy, J.A.: Pancyclic graphs I. J. Comb. Theory 11, 80–84 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bondy, J.A.: Pancyclic graphs: recent results, infinite and finite sets. In: Colloq. Math. Soc. János Bolyai, Keszthely, Hungary, pp. 181–187 (1973)

  5. Bondy, J.A.: A remark on two sufficient conditions for Hamilton cycles. Discret. Math. 22, 191–194 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)

    Book  MATH  Google Scholar 

  7. Borchert, A., Nicol, S., Oellermann, O.R.: Global cycle properties of locally isometric graphs. Discret. Appl. Math. 205, 16–26 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chartrand, G., Pippert, R.E.: Locally connected graphs. Časopis Pěst. Mat. 99, 158–163 (1974)

    MathSciNet  MATH  Google Scholar 

  9. Chen, G., Saito, A., Shan, S.: The existence of a 2-factor in a graph satisfying the local Chvátal-Erdős Condition. SIAM J. Discret. Math. 27(4), 1788–1799 (2014)

    Article  MATH  Google Scholar 

  10. Chvátal, V., Erdős, P.: A note on Hamiltonian circuits. Discret. Math. 2, 111–113 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  11. Clark, L.: Hamiltonian properties of connected locally connected graphs. Congr. Numer. 32, 199–204 (1981)

    MathSciNet  MATH  Google Scholar 

  12. de Wet, J.P.: Local Properties of Graphs. Doctoral thesis, University of South Africa, Pretoria (2016)

  13. de Wet, J.P., van Aardt, S.A.: Traceabiltity of locally traceable and locally hamiltonian graphs. Discret. Math. Theor. Comput. Sci. 17, 245–262 (2016)

    MATH  Google Scholar 

  14. de Wet, J., Frick, M., van Aardt, S.A.: Hamiltonicity of locally traceable and locally hamiltonian graphs submitted

  15. Goldner, A., Harary, F.: Note on a smallest nonhamiltonian maximal planar graph. Bull. Malays. Math. Soc. 6(1), 41–42 (1975)

    Google Scholar 

  16. Gordon, V.S., Orlovich, Y.L., Potts, C., Strusevich, V.A.: Hamiltonian properties of locally connected graphs with bounded vertex degree. Discret. Appl. Math. 159, 1759–1774 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  17. Hasratian, A.S., Khachatrian, N.K.: Some localization theorems on hamiltonian circuits. J. Comb. Theory Ser. B 49, 287–294 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  18. Hendry, G.R.T.: A strengthening of Kikust’s theorem. J. Graph Theory 13, 257–260 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  19. Hendry, G.R.T.: Extending cycles in graphs. Discret. Math. 85, 59–72 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kikust, P.B.: The existence of a hamiltonian cycle in a regular graph of degree 5 [Russian, Latvian summary]. Latv. Math. Yearb. 16, 33–38 (1975)

    MathSciNet  Google Scholar 

  21. Li, M., Corneil, D.G., Mendelsohn, E.: Pancyclicity and NP-completeness in planar graphs. Discret. Appl. Math. 98(3), 219–2250 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  22. Lovász, L., Neumann-Lara, V., Plummer, M.: Mengerian theorems for paths of bounded length. Period. Math. Hung. 9(4), 269–276 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  23. Oberly, D.J., Sumner, D.P.: Every connected, locally connected nontrivial graph with no induced claw is hamiltonian. J. Graph Theory 3, 351–356 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  24. Ore, O.: Note on hamilton circuits. Am. Math. Monthly 67, 55 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  25. Pareek, C.M.: On the maximum degree of locally hamiltonian non-hamiltonian graphs. Util. Math. 23, 103–120 (1983)

    MathSciNet  MATH  Google Scholar 

  26. Pareek, C.M., Skupień, Z.: On the smallest non-hamiltonian locally hamiltonian lagów. J. Univ. Kuwait Sci. 10, 9–16 (1983)

    MathSciNet  MATH  Google Scholar 

  27. Saito, A.: Chvátal-Erdős Theorem: Old Theorem with New Aspects, Computational Geometry and Graph Theory. Lecture Notes in Computer Science, vol. 4535, pp. 191–200. Springer, Berlin (2008)

  28. Sedlác̃ek, J.: On local properties of finite graphs. Graph Theory, Lagów. Lecture Notes in Mathematics, vol. 1018, pp. 242–247. Springer-Verlag (1983)

  29. Skupień, Z.: Locally hamiltonian graphs and Kuratowski’s theorem. Bull. Acad. Poln. Sci. Sér. Sci. Math. Astronom. Phys. 13, 615–619 (1965)

    MathSciNet  MATH  Google Scholar 

  30. Skupień, Z.: Locally hamiltonian and planar graphs. Fundam. Math. 58, 193–200 (1966)

    MathSciNet  MATH  Google Scholar 

  31. van Aardt, S.A., Frick, M., Oellermann, O.R., de Wet, J.: Global cycle properties in locally connected, locally traceable and locally hamiltonian graphs. Discret. Appl. Math. 205, 171–179 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  32. Zykov, A.A.: Problem 30. In: Fiedler M (ed.) Theory of Graphs and Applications (Proc. Symp. Smolenice, Prague), pp. 164–165 (1964)

Download references

Acknowledgements

The authors wish to express gratitude to the Banff International Research Station for their support of the focused research workshop “Local Properties in Graphs that imply Global Cycle Properties” (15frg184), where this paper originated.

Author information

Authors and Affiliations

  1. University of Winnipeg, Winnipeg, Canada

    Ortrud R. Oellermann & Johan P. de Wet

  2. University of South Africa, Pretoria, South Africa

    Susan A. van Aardt & Marietjie Frick

  3. Converse College, Spartarburg, South Carolina, USA

    Jean E. Dunbar

Authors
  1. Susan A. van Aardt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean E. Dunbar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marietjie Frick
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ortrud R. Oellermann
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Johan P. de Wet
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ortrud R. Oellermann.

Additional information

S. A. van Aardt: Supported by the National Research Foundation of S.A., Grant Number 81075, M. Frick: Supported by the National Research Foundation of S.A., Grant Number 81004, O. R. Oellermann: Supported by an NSERC Grant CANADA, Grant Number RGPIN-2016-05237.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

van Aardt, S.A., Dunbar, J.E., Frick, M. et al. On Saito’s Conjecture and the Oberly–Sumner Conjectures. Graphs and Combinatorics 33, 583–594 (2017). https://doi.org/10.1007/s00373-017-1820-5

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-017-1820-5

Keywords

Mathematics Subject Classification

Search

Navigation