×

On a class of Hamiltonian polytopes. (English) Zbl 0655.05045

Let \({\mathcal S}(p,q)\) denote the class of simple 3-polytopal graphs all of whose edges are incident with two p-gons or a p-gon and a q-gon, \(p\neq q\), p,q\(\geq 3\). In this paper it is shown that all graphs of the class \({\mathcal S}(5,q)\) for \(3\leq q\leq 12\), \(q\neq 5\) are Hamiltonian, using the following proposition due to S. K. Stein: A simple 3-polytopal graph G is Hamiltonian if and only if its dual \(G^*\) has point- arboricity equal to 2 [Bull. Am. Math. Soc. 76, 805-806 (1970; Zbl 0194.560)]. The theorem in the present paper supplements the known results of P. R. Goodey that all graphs of the classes \({\mathcal G}(3,6)\) and \({\mathcal G}(4,6)\) are Hamiltonian, where \({\mathcal G}(p,q)\) denotes the class of 3-connected 3-valent planar graphs, i.e. simple 3-polytopal graphs, all of whose faces are p-gons and q-gons, \(p<q\), \(p\geq 3\) [Isr. J. Math. 22, 52-56 (1975; Zbl 0317.05114); J. Graph Theory 1, 181-185 (1977; Zbl 0379.05037)].
Reviewer: I.Tomescu

MSC:

05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chartrand, G.; Kronk, H. V., The point-arboricity of planar graph, J. London Math. Soc., 44, 612-616 (1969) · Zbl 0175.50505
[2] Goodey, P. R., Hamiltonian circuits in polytopes with even sided faces, Israel J. Math., 22, 52-56 (1975) · Zbl 0317.05114
[3] Goodey, P. R., A class of hamiltonian polytopes, J. Graph Theory, 1, 181-185 (1977) · Zbl 0379.05037
[4] Grünbaum, B., Convex Polytopes (1967), Interscience: Interscience London · Zbl 0163.16603
[5] Jendrol̆, S.; Tkác̆, M., On the simplicial 3-polytopes with only two types of edges, Discrete Math., 48, 229-241 (1984) · Zbl 0536.52003
[6] Owens, P. J., Simple 3-polytopal graphs with edges of only two types and shortness coeffecients, Discrete Math., 59, 107-114 (1986) · Zbl 0586.05027
[7] Owens, P. J., Regular planar graphs with faces of only two types and shortness parameters, J. Graph Theory, 8, 253-275 (1984) · Zbl 0541.05037
[8] Stein, S. K., B-sets and coloring problems, Bull. Amer. Math. Soc., 76, 805-806 (1970) · Zbl 0194.56004
[9] Zaks, J., Non-hamiltonian simple 3-polytopes having just two types of faces, Discrete Math., 29, 87-101 (1980) · Zbl 0445.05065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.