Pancyclism and bipancyclism of Hamiltonian graphs
The following statements are well known: (1) [\textit{J. A. Bondy}, J. Comb. Theory, Ser. B 11, 80-84 (1971; Zbl 0183.523)]: Let \(G\) be a graph on \(n \geq 3\) vertices satisfying the condition \((*)\): \((x,y) \notin E(G)\) implies that \(d(x)=d(y) \geq n\) for \(x,y \in V(G)\). Then \(G\) is either pancyclic or the complete bipartite graph \(K_{n/2,n/2}\). (2) [\textit{E. Schmeichel} and \textit{J. Mitchem}, J. Graph Theory 6, 429-439 (1982; Zbl 0502.05036)]: Let \(G=(X,Y;E)\) be a bipartite graph with \(| X | = | Y | = n \neq 3\) satisfying the condition \((**)\): \(d(x_ k) \leq k\) implies \(d(y_{n-k}) \geq n-k+1\) for every \(k=1,\dots,n-1\), where \(d(x_ 1) \leq d(x_ 2) \leq\cdots \leq d(x_ n)\) and \(d(y_ 1) \leq d(y_ 2) \leq \cdots \leq d(y_ n)\) are the degree sequences of \(X\) and \(Y\), respectively. Then \(G\) is bipancyclic. Obviously, \((**)\) is fulfilled if the following condition \((*_ **)\) is satisfied: \((x,y) \notin E\) implies that \(d(x) + d(y) \geq n+1\) for \(x \in X\), \(y \in Y\). Thus, taking \((*_ **)\) instead of \((**)\) we get a corollary \((2)^*\) of (2). The author proves that the assertions (1) and \((2)^*\) remain valid if \((*)\) and \((*_ **)\), respectively, are replaced by the weaker conditions \((*)'\): \(G\) is Hamiltonian and there exists a vertex \(x \in V(G)\) such that \(d(x)+d(y) \geq n\) for each vertex \(y \in V(G)\) not adjacent to \(x\); \((*_ **)'\): \(G\) is Hamiltonian and there exists a vertex \(x \in X\) such that \(d(x)+d(y) \geq n+1\) for each \(y \in Y\) not adjacent to \(x\). It is further shown that the bounds \(n\) and \(n+1\), respectively, in these conditions are best possible.
scientific article; zbMATH DE number 562400