Longest cycles in polyhedral graphs
For a graph \(G\), let \(\nu(G)\) and \(c(G)\) be the number of vertices and the circumference of \(G\), respectively. If \(\Gamma\) is a family of graphs, the shortness exponent of \(\Gamma\), \(\sigma(\Gamma)\), is defined as \[ \sigma(\Gamma):=\liminf_{G\in \Gamma}{\log c(G)\over\log\nu(G)}. \] Several families of polyhedral graphs \(\Gamma\) are known such that \(\sigma(\Gamma)<1\) and \(\sigma(\Gamma^*)<1\),where \(\Gamma^*=\{G^*\mid G\) is in \(\Gamma\) and \(G^*\) is dual to \(G\}\). Constructed is a sequence \(\{G_ n\}\) of polyhedral graphs having only vertices of degree 3 and 8 and only triangles and octagons as faces such that \(\sigma(\{G_ n\})<1\) and \(\sigma(\{G^*_ n\})<1\). The construction starts with a certain non-Hamiltonian graph \(G_ 1\) on 14 vertices. It proceeds by a process of replacing each 3-valent vertex by a modified \(G_ 1\).
- Longest Simple Paths in Polyhedral Graphs
- On shortness coefficients of simple 3-polytopal graphs with only one type of faces besides triangles
- On shortness exponents of families of graphs
- Regular planar graphs with faces of only two types and shortness parameters
- Shortness exponents of families of graphs
- The longest cycle problem is polynomial on interval graphs
- Regular planar graphs with faces of only two types and shortness parameters
- Determinants and Longest Cycles of Graphs
- Finding paths and cycles of superpolylogarithmic length
- Some new results about the shortness exponent in polyhedral graphs
- On longest cycles and strongly linking vertex sets
- Lattice graphs with non-concurrent longest cycles
- scientific article; zbMATH DE number 889955 (Why is no real title available?)
- scientific article; zbMATH DE number 1444473 (Why is no real title available?)
- On short cycles through prescribed vertices of a polyhedral graph
- scientific article; zbMATH DE number 4189768 (Why is no real title available?)
This page was built for publication: Longest cycles in polyhedral graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690053)
