Bipartite regular graphs and shortness parameters (Q1083455): Difference between revisions

\textit{B. Grünbaum} and \textit{H. Walther} [J. Comb. Theory, Ser. A 14, 364-385 (1973; Zbl 0263.05103)] defined the shortness exponent \(\sigma\) (\({\mathcal G})\) and shortness coefficient \(\rho\) (\({\mathcal G})\) of an infinite class of graphs \({\mathcal G}\) as \(\sigma\) (\({\mathcal G})= \inf_{G\in {\mathcal G}}\frac{\log h(G)}{\log v(G)}\), \(\rho\) (\({\mathcal G})= \inf_{G\in {\mathcal G}}\frac{h(G)}{v(G)}\) where v(G) is the order of G and h(G) is the length of a longest cycle of G. Let \({\mathcal B}_ k\) denote the class of all k- connected k-regular bipartite graphs and \(C_ r\) the class of all cyclically r-edge-connected graphs. It is shown that \(\sigma\) (\({\mathcal B}_ k)<1\) for \(k\geq 4\) and that \(\rho\) (\({\mathcal B}_ 3\cap C_ 4)<1\). The sequences of graphs leading to these results have the same starting point, the recent construction by \textit{M. N. Ellingham} and \textit{J. D. Horton} [J. Comb. Theory, Ser. B 34, 350-353 (1983; Zbl 0516.05033)] of a member of \({\mathcal B}_ 3\cap C_ 4\) having 54 vertices. The author closes with a correction to a previous result of his paper in Discrete Math. 44, 327-330 (1983; Zbl 0508.05044).