Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-30T17:08:18.089Z Has data issue: false hasContentIssue false
  • English
  • Français

On r-regular r-connected non-hamiltonian graphs

Published online by Cambridge University Press:  17 April 2009

Brad Jackson  and
T. D. Parsons
Brad Jackson
Affiliation:
Department of Mathematics, University of California, Santa Cruz, Santa Cruz, California 95064, USA;
T. D. Parsons
Affiliation:
Department of Mathematics, College of Science, Pennsylvania State University, University Park, Pennsylvania 16802, 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.

Some methods are given for constructing regular r-valent r-connected non-hamiltonian graphs; often the graphs are also non-r-edge-colorable. The extent of the class of such graphs constructible from these methods and previous methods is discussed.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 24 , Issue 2 , October 1981 , pp. 205 - 220
Copyright
Copyright © Australian Mathematical Society 1981

References

[1]Babai, L., Problem 18, Unsolved problems, Summer Research Workshop in Algebraic Combinatorics (Mathematics Department, Simon Fraser University, 07 1979).Google Scholar
[2]Bondy, J.A. and Murty, U.S.R., Graph theory with applications (American Elsevier, New York, 1976).Google Scholar
[3]Bondy, J.A. and Simonovits, M., “Longest cycles in 3-connected 3-regular graphs”, Canad. J. Math. 32 (1980), 987–992.Google Scholar
[4]Chetwynd, Amanda G. and Wilson, Robin J., “Snarks and supersnarks”,Proceedings of the Fourth International Conference on Graph Theory, Kalamazoo, Michigan (John Wiley & Sons, New York, to appear).Google Scholar
[5]Ford, L.R. Jr. and Fulkerson, D.R., “Maximal flow through a network”, Canad. J. Math. 8 (1956), 399–404.CrossRefGoogle Scholar
[6]Grünbaum, Branko, “Polytopes, graphs, and complexes”, Bull. Amer. Math. Soc. 76 (1970), 1131–1201.Google Scholar
[7]Grünbaum, Branko, “Vertices missed by longest paths or circuits”, J. Combin. Theory Ser. A 17 (1974), 31–38.Google Scholar
[8]Harary, Frank, “The maximum connectivity of a graph”, Proc. Nat. Acad. Sci. U.S.A. 48 (1962), 1142–1146.CrossRefGoogle ScholarPubMed
[9]Harary, Frank, Graph theory (Addison-Wesley, Reading, Massachusetts; Menlo Park, California; London; 1969).CrossRefGoogle Scholar
[10]Holton, D.A., McKay, B.D. & Plummer, M.D., “Cycle through specified vertices in 3-connected cubic graphs” (Research Report 38. University of Melbourne, Parkville, Victoria 1979).Google Scholar
[11]Isaacs, Rufus, “Infinite families of nontrivial trivalent graphs which are not Tait colorable”, Amer. Math. Monthly 82 (1975), 221–239.Google Scholar
[12]Jackson, Brad and Parsons, T.D., “Longest cycles in r-regular r-connected graphs”, submitted.Google Scholar
[13]Jackson, Brad and Parsons, T.D., “A shortness exponent for r-regular r-connected graphs”, submitted.Google Scholar
[14]Meredith, G.H.J., “Regular n-valent, n-connected nonhamiltonian non-n-edge-colorable graphs”, J. Combin. Theory Ser. B 14 (1973), 55–60.CrossRefGoogle Scholar
[15]Petersen, Julius, “Die Theorie der regulären Graphs”, Acta Math. 15 (1891), 193–220.Google Scholar
[16]Thomassen, Carsten, “A minimal condition implying a special K 4-subdivision in a graph”, Arch. Math. 25 (1974), 210–215.CrossRefGoogle Scholar
[17]Tutte, W.T., “On Hamiltonian circuits”, J. London Math. Soc. 21 (1946), 98–101.CrossRefGoogle Scholar
[18]Tutte, W.T., “A geometrical version of the four color problem”, Combinatorial mathematics and its applications, 553–560 (Proc. Conf. Univ. North Carolina,Chapel Hill, North Carolina,1967.University of North Carolina Press, Chapel Hill, New York, 1969).Google Scholar
[19]Zamfirescu, Tudor, “On longest paths and circuits in graphs”, Math. Scand. 38 (1976), 211–239.Google Scholar