×

Regular planar graphs with faces of only two types and shortness parameters. (English) Zbl 0541.05037

Für einen Graphen G sei h(G) die Länge enes maximalen Kreises und v(G) die Anzahl seiner Ecken. Ist \({\mathcal G}\) eine beliebige Familie von Graphen, so heißt \(\rho({\mathcal G}):=\lim \inf(h(G)/v(G))\) der Längenkoeffizient (shortness coefficient) und \(\sigma({\mathcal G}):=\lim \inf(\log h(G)/\log v(G))\) der Längenexponent (shortness exponent) von \({\mathcal G}\). Der Autor untersucht den Längenexponenten in der Klasse \(G_ r(p,q)\), \(p<q\) der r-valenten, planaren Graphen, deren Flächen sämtlich entweder p-gons oder q-gons sind. Im Falle \(r=3\), \(p=4\) q ungerade, ist \(\rho(G_ 3(4,5))=1\) und nach einem Resultat von H. Walther, über das Problem der Existenz von Hamilton-Kreisen in planaren, regulären Graphen [Math. Nachr. 39, 277-296 (1969; Zbl 0169.264)] gilt \((G_ 3(5,q))<1\) für \(q\geq 9\). Für den verbleibenden Fall \(q=7\) zeigt der Autor \(\rho(G_ 3(5,7))<1.\) Dieses Resultat ergibt zugleich eine Verbesserung von \(\rho(G_ 3(5,9))\) und ein einfacheres Beispiel als das von Walther konstruierte. Im Falle \(r=4\) zeigt der Autor für den Längenexponenten \(\sigma(G_ 4(3,q)<1\) für alle \(q\geq 12\). Dieses Resultat verbessert ein Ergebnis von J. Harant über den Shortness Exponent regulärer Polyedergraphen mit genau zwei Typen von Elementarflächen [Thesis A, Ilmenau Institute of Technology (1982)]. Weitere Resultate betreffen den Längenexponenten von Klassen zyklisch- s-kantenzusammenhängender Graphen. Sei \({\mathcal C}(s)\) die Klasse der zyklisch s-zusammenhängenden Graphen und sei \(P_ r(t)\) die Klasse der r-valenten planaren Graphen mit höchstens t verschiedenen Typen von Flächen. Der Autor zeigt \(\sigma({\mathcal C}(6)\cap P_ 4(2))<1\) und \(\sigma({\mathcal C}(6)\cap G_ 5(3,q))<1\) für \(q\geq 14\), \(q\not\equiv 0\) mod 3.
Reviewer: F.Hering

MSC:

05C38 Paths and cycles
05C35 Extremal problems in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 0169.264
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Conjecture 5. In Recent Progress in Combinatorics, Ed. Academic, New York (1969).
[2] Hamiltonian lines in cubic graphs. In Proceedings of the International Symposium on the Theory of Graphs, Rome 1966. Gordon and Breach, New York; Dunod, Paris (1967).
[3] and , Examples and Counterexamples in Graph Theory. North-Holland, New York (1978).
[4] Goodey, Israel J. Math. 22 pp 52– (1975)
[5] Grünbaum, Aequationes Math. 14 pp 191– (1976)
[6] Grünbaum, J. Combinatorial Theory Ser. A 14 pp 364– (1973)
[7] Uber den Shortness Exponent regulärer Polyedergraphen mit genau zwei Typen von Elementarflächen. Thesis A, Ilmenau Institute of Technology (1982).
[8] Owens, Discrete Math. 36 pp 227– (1981) · Zbl 0473.05043 · doi:10.1016/0012-365X(81)90239-9
[9] Owens, Discrete Math. 39 pp 199– (1982)
[10] Owens, J. Graph Theory 6 pp 473– (1982)
[11] Non-Hamiltonian simple 3-polytopes with only one type of faces besides triangles. In Convexity and Graph Theory, and , Eds. North-Holland, New York. To appear. · Zbl 0571.05033
[12] Walther, Math. Nachr. 39 pp 277– (1969)
[13] Walther, Discrete Math. 33 pp 107– (1981)
[14] Zaks, Discrete Math. 17 pp 317– (1977)
[15] Zaks, Discrete Math. 29 pp 87– (1980)
[16] Non-Hamiltonian simple planar graphs. In Theory and Practice of Combinatorics, , and , Eds. North-Holland, New York (1982). · Zbl 0493.05022
[17] Zaks, Aequationes Math.
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.