Simple 3-polytopal graphs with edges of only two types and shortness coefficients.

*(English)*Zbl 0586.05027Simple planar 3-connected trivalent graphs are considered with only two types of faces: 5-gons and q-gons, in which no two q-gons have a common edge. For any \(q\geq 28\) infinitely many non-Hamltonian graphs are constructed. It also follows that for large enough q values any cycle in these graphs misses at least 1/60 of the vertices, thereby radically improving previous results. For all \(q\geq 16\) infinite families of graphs (not necessarily non-Hamiltonian) are constructed. It is also shown that that any graph with \(q\geq 6\) is cyclically 4-edge connected.

Reviewer: F.Plastria

##### MSC:

05C38 | Paths and cycles |

05C40 | Connectivity |

51M20 | Polyhedra and polytopes; regular figures, division of spaces |

05C45 | Eulerian and Hamiltonian graphs |

##### Keywords:

planar 3-connected graphs; shortness coefficient; non-Hamltonian graphs; cyclically 4-edge connected
Full Text:
DOI

**OpenURL**

##### References:

[1] | Faulkner, G.B; Younger, D.H, Non-Hamiltonian cubic planar maps, Discrete math., 7, 67-74, (1974) · Zbl 0271.05106 |

[2] | Grünbaum, B; Malkevitch, J, Pairs of edge-disjoint Hamiltonian circuits, Aequationes math., 14, 191-196, (1976) · Zbl 0331.05118 |

[3] | Grünbaum, B; Walther, H, Shortness exponents of families of graphs, J. combin. theory ser. A, 14, 364-385, (1973) · Zbl 0263.05103 |

[4] | Harant, J, Uber den shortness exponent regulärer polyedergraphen mit genau zwei typen von elementrflächen, () |

[5] | Jendroľ, S; Tkáč, 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, Shortness parameters of families of regular planar graphs with two or three types of face, Discrete math., 39, 199-209, (1982) · Zbl 0492.05051 |

[7] | Owens, P.J, Cyclically 5-edge-connected cubic planar graphs and shortness coefficients, J. graph theory, 6, 473-479, (1982) · Zbl 0502.05032 |

[8] | 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 |

[9] | Owens, P.J, Shortness parameters for planar graphs with faces of only one type, J. graph theory, 9, 381-395, (1985) · Zbl 0584.05047 |

[10] | Walther, H, Note on two problems of J. zaks concerning Hamiltonian 3-polytopes, Discrete math., 33, 107-109, (1981) · Zbl 0476.05051 |

[11] | 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.