Note on Locating Pairs of Vertices on Hamiltonian Cycles | Graphs and Combinatorics Skip to main content
Springer Nature Link
Log in

Note on Locating Pairs of Vertices on Hamiltonian Cycles

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

Abstract

Given a fixed positive integer k ≥ 2, let G be a simple graph of order n ≥ 6k. It is proved that if the minimum degree of G is at least n/2 + 1, then for every pair of vertices x and y, there exists a Hamiltonian cycle such that the distance between x and y along that cycle is precisely k.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Chartrand G., Lesniak L.: Graphs and Digraphs. Chapman and Hall, London (2005)

    MATH  Google Scholar 

  2. Dirac G.A.: Some theorems on abstract graphs. Proc. London Math. Soc. 2, 69–81 (1952)

    Article  MATH  MathSciNet  Google Scholar 

  3. Faudree R., Gould R., Jacobson M., Magnant C.: Distributing vertices on Hamiltonian cycles. J. Graph Theory 69, 28–45 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  4. Faudree, R., Li, H.: Locating pairs of vertices on a Hamiltonian cycle. Discrete Math. 312, 2707–2719 (2013)

    Google Scholar 

  5. Kaneko A., Yoshimoto K.: On a Hamiltonian cycle in which specified vertices are uniformly distributed. J. Combin. Theory Ser. B 81, 309–324 (2001)

    Article  MathSciNet  Google Scholar 

  6. Moon J., Moser L.: On hamiltonian bipartite graphs. Israel J. Math. 1, 163–165 (1963)

    Article  MATH  MathSciNet  Google Scholar 

  7. St, C., Nash-Williams, J.A.: Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency, in Studies in Pure Mathematics, pp. 157–183. Academic Press, London (1971)

  8. Sárközy G., Selkow S.: Distributing vertices along a Hamiltonian cycle in Dirac graphs. Discrete Math. 308, 5757–5770 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  9. Whitney H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150–168 (1932)

    Article  MathSciNet  Google Scholar 

  10. Williamson J.: Panconnected graphs. II. Period. Math. Hungar. 8, 105–116 (1977)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The University of Memphis, Memphis, 38152, TN, USA

    Ralph J. Faudree & Jeno Lehel

  2. Nikon University, Tokyo, 101-8308, Japan

    Kiyoshi Yoshimoto

Authors
  1. Ralph J. Faudree
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jeno Lehel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kiyoshi Yoshimoto
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeno Lehel.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Faudree, R.J., Lehel, J. & Yoshimoto, K. Note on Locating Pairs of Vertices on Hamiltonian Cycles. Graphs and Combinatorics 30, 887–894 (2014). https://doi.org/10.1007/s00373-013-1325-9

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-013-1325-9

Keywords

Mathematics Subject Classification (2000)

Search

Navigation