Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-10T05:14:09.634Z Has data issue: false hasContentIssue false
  • English
  • Français

Cyclability of r-regular r-connected graphs

Published online by Cambridge University Press:  17 April 2009

W.D. McCuaig  and
M. Rosenfeld
W.D. McCuaig
Affiliation:
Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, CanadaV5AIS6 Department of Mathematics, Ben Gurion University of Negev, Beer Sheva 84120, Israel Department of Mathematics, University of Washington, Seattle, Washington 98195, USA.
M. Rosenfeld
Affiliation:
Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, CanadaV5AIS6 Department of Mathematics, Ben Gurion University of Negev, Beer Sheva 84120, Israel Department of Mathematics, University of Washington, Seattle, Washington 98195, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

For each value of r ≥ 4, r even, we construct infinitely many r-regular, r-connected graphs whose cyclability is not greater than 6r − 4 if r = 0 (mod 4) and 8r − 5 if r ≡ 2 (mod 4).

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 29 , Issue 1 , February 1984 , pp. 1 - 11
Copyright
Copyright © Australian Mathematical Society 1984

References

[1]Bondy, J.A. and Murty, U.S.R., Graph theory with applications (American Elsevier, New York, 1976).Google Scholar
[2]Chvátal, Vaclav, “New directions in Hamiltonian graph theory”, New directions in the theory of graphs, 65–95 (Proc. Third Ann Arbor Conf. on Graph Theory, University of Michigan, Ann Arbor, Michigan, 1971. Academic Press, New York, 1973).Google Scholar
[3]Holton, D.A., “Cycles through specified vertices in k-connected regular graphs”, Ars Combin. 13 (1982), 129–143.Google Scholar
[4]Holton, D.A., McKay, B.D., Plummer, M.D. and Thomassen, C., “A nine point theorem for 3-connected graphs”, Combinatoria 2 (1982), 53–62.CrossRefGoogle Scholar
[5]Jackson, Brad and Parsons, T.D., “On r-regular r-connected non-Hamiltonian graphs”, Bull. Austral. Math. Soc. 24 (1981), 205–220.CrossRefGoogle Scholar
[6]Jackson, Brad and Parsons, T.D., “A shortness exponent for r-regular r-connected graphs”, J. Graph Theory 6 (1982), 169–176.CrossRefGoogle Scholar
[7]Kelmans, A.K. and Lomonosov, M.V., “When m vertices in a k-connected graph cannot be walked round along a simple cycle”, Discrete Math. 38 (1982), 317–322.CrossRefGoogle Scholar
[8]Meredith, G.H.J., “Regular n-valent n-connected non-Hamiltonian non-n-edge colourable graphs”, J. Combin. Theory Ser. B 14 (1973), 55–60.CrossRefGoogle Scholar
[9]Rosenfeld, M., “Are all simple 4-polytopes Hamiltonian?”, Israel J. Math. (to appear).Google Scholar