Hamiltonicity in multitriangular graphs

Peter J. Owens; Hansjoachim Walther

Discussiones Mathematicae Graph Theory (1995)

  • Volume: 15, Issue: 1, page 77-88
  • ISSN: 2083-5892

Abstract

top
The family of 5-valent polyhedral graphs whose faces are all triangles or 3s-gons, s ≥ 9, is shown to contain non-hamiltonian graphs and to have a shortness exponent smaller than one.

How to cite

top

Peter J. Owens, and Hansjoachim Walther. "Hamiltonicity in multitriangular graphs." Discussiones Mathematicae Graph Theory 15.1 (1995): 77-88. <http://eudml.org/doc/270460>.

@article{PeterJ1995,
abstract = {The family of 5-valent polyhedral graphs whose faces are all triangles or 3s-gons, s ≥ 9, is shown to contain non-hamiltonian graphs and to have a shortness exponent smaller than one.},
author = {Peter J. Owens, Hansjoachim Walther},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {polyhedral graphs; longest cycles; shortness exponent; hamiltonicity; multitriangular graphs; longest cycle; faces; triangles; Tutte subgraphs},
language = {eng},
number = {1},
pages = {77-88},
title = {Hamiltonicity in multitriangular graphs},
url = {http://eudml.org/doc/270460},
volume = {15},
year = {1995},
}

TY - JOUR
AU - Peter J. Owens
AU - Hansjoachim Walther
TI - Hamiltonicity in multitriangular graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 1
SP - 77
EP - 88
AB - The family of 5-valent polyhedral graphs whose faces are all triangles or 3s-gons, s ≥ 9, is shown to contain non-hamiltonian graphs and to have a shortness exponent smaller than one.
LA - eng
KW - polyhedral graphs; longest cycles; shortness exponent; hamiltonicity; multitriangular graphs; longest cycle; faces; triangles; Tutte subgraphs
UR - http://eudml.org/doc/270460
ER -

References

top
  1. [1] E. J. Grinberg, Planehomogeneous graphs of degree three without Hamiltonian circuits, Latvian Math. Yearbook 4 (1968) 51-58 (in Russian). Zbl0185.27901
  2. [2] B. Grünbaum and H. Walther, Shortness exponents of families of graphs, J. Combin. Theory (A) 14 (1973) 364-385, doi: 10.1016/0097-3165(73)90012-5. Zbl0263.05103
  3. [3] J. Harant, Über den Shortness Exponent regulärer Polyedergraphen mit genau zwei Typen von Elementarflächen, Thesis A, Ilmenau Institute of Technology (1982). 
  4. [4] D. A. Holton and B. D. McKay, The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Combin. Theory (B) 45 (1988) 305-319, with correction, J. Combin. Theory (B) 47 (1989) 248. Zbl0607.05051
  5. [5] P. J. Owens, Non-hamiltonian simple 3-polytopes whose faces are all 5-gons or 7-gons, Discrete Math. 33 (1981) 107-109. Zbl0473.05043
  6. [6] P. J. Owens, Regular planar graphs with faces of only two types and shortness parameters, J. Graph Theory 8 (1984) 253-275, doi: 10.1002/jgt.3190080207. Zbl0541.05037
  7. [7] P. J. Owens, Simple 3-polytopal graphs with edges of only two types and shortness coefficients, Discrete Math. 59 (1986) 107-114, doi: 10.1016/0012-365X(86)90074-9. Zbl0586.05027
  8. [8] P. J. Owens, Shortness exponents, simple polyhedral graphs and large bridges, unpublished. 
  9. [9] M. Tkáč, Shortness coefficients of simple 3-polytopal graphs with edges of only two types, Discrete Math. 103 (1992) 103-110, doi: 10.1016/0012-365X(92)90045-H. Zbl0776.05093
  10. [10] M. Tkáč, Simple 3-polytopal graphs with edges of only two types and shortness coefficients, Math. Slovaca 42 (1992) 147-152. Zbl0768.05065
  11. [11] M. Tkáč, On shortness coefficients of simple 3-polytopal graphs with edges of only one type of face besides triangles, Discrete Math. 128 (1994) 407-413, doi: 10.1016/0012-365X(94)90133-3. Zbl0798.05018
  12. [12] W. T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946) 98-101, doi: 10.1112/jlms/s1-21.2.98. Zbl0061.41306
  13. [13] H. Walther, Über das Problem der Existenz von Hamiltonkreisen in planaren regulären Graphen, Math. Nachr. 39 (1969) 277-296, doi: 10.1002/mana.19690390407. Zbl0169.26401
  14. [14] H. Walther, Note on the problems of J.Zaks concerning Hamiltonian 3-polytopes, Discrete Math. 33 (1981) 107-109, doi: 10.1016/0012-365X(81)90265-X. 
  15. [15] H. Walther, A non-hamiltonian five-regular multitriangular polyhedral graph (to appear). Zbl0854.05065
  16. [16] J. Zaks, Non-Hamiltonian non-Grinbergian graphs, Discrete Math. 17 (1977) 317-321, doi: 10.1016/0012-365X(77)90165-0. Zbl0357.05052
  17. [17] J. Zaks, Non-Hamiltonian simple 3-polytopes having just two types of faces, Discrete Math. 29 (1980) 87-101, doi: 10.1016/0012-365X(90)90289-T. Zbl0445.05065
  18. [18] J. Zaks, Non-hamiltonian simple planar graphs, in: Annals of Discrete Math. 12 (North - Holland, 1982) 255-263. Zbl0493.05022

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.