Pancyclism and bipancyclism of Hamiltonian graphs
type: Item
instance of: scholarly article
title: Pancyclism and bipancyclism of Hamiltonian graphs
zbMATH Open document ID: 0795.05086
author: Shemin Zhang
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-06-06T00:00:00Z
review text: 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.
reviewed by: Günter Schaar
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 562400
zbMATH Keywords: Hamiltonian graph
zbMATH Keywords: pancyclic graph
zbMATH Keywords: bipancyclic bipartite graph
zbMATH Keywords: bipartite graph
zbMATH Keywords: bounds
MaRDI profile type: Publication
full work available at URL: jctb.1994.1010
OpenAlex ID: W2026854216
DOI: 10.1006/JCTB.1994.1010
Recommended article: Q3680866
Recommended article: A condition for a Hamiltonian bipartite graph to be bipancyclic
Recommended article: Q4809394
Recommended article: Locally pancyclic graphs
Recommended article: Q3353047
Recommended article: Q3974704
Recommended article: Longest cycles in certain bipartite graphs
Recommended article: Q3317137
Recommended article: A cycle structure theorem for Hamiltonian graphs
description: scientific article; zbMATH DE number 562400