×

Pancyclic and bipancyclic graphs. (English) Zbl 1356.05002

SpringerBriefs in Mathematics. Cham: Springer (ISBN 978-3-319-31950-6/pbk; 978-3-319-31951-3/ebook). xii, 108 p. (2016).
The book works on the topic of pancyclicity. Cycle structures in graphs have been studied for a long time. J. A. Bondy [J. Comb. Theory, Ser. B 11, 80–84 (1971; Zbl 0183.52301)] introduced the idea of pancyclicity. A pancyclic graph is one that contains cycles of every possible length. When the graph under consideration is bipartite, it contains only cycles of even order. Thus, the corresponding defintion is that of a bipancyclic graph, which contains cycles of every possible even length. In particular, Bondy [loc. cit.] raised the metaconjecture that almost any nontrivial conditions on a graph which implies that the graph is Hamiltonian also implies that the graph is pancyclic. This became a good motivation for the study of pancyclicity, for it not only explain the reason why pancyclic graphs are of interest, but also provides a starting point for researchers to generalize the existing conditions for Hamiltonicity to pancyclicity.
Following the idea of Bondy, many sufficient conditions for pancyclicity has been raised, mostly migrated from those for Hamiltonicity. In Chapter 2 of the book, several important degree conditions for Hamiltonicity are reviewed. In Chapter 3, their generalizations for pancyclicity are treated, together with some results on pancyclic graph products and some open problems.
Chapter 4 and Chapter 5, as well as Chapter 7 and Chapter 8 which work on the corresponding problems on bipancyclic graphs, contain many of the author’s own contributions for minimal pancyclicity and unique pancyclicity.
In Chapter 4, minimal pancyclicity is considered. Here, a minimally pancyclic graph is defined to be a pancyclic graph on \(n\) vertices with minimum number of edges. A pancyclic graph can be obtained by adding chords to a Hamiltonian cycle. The number of chords to be added, i.e. the difference between the number of edges and the number of vertices is defined to be the excess of the graph. Therefore, to get a minimal pancyclic graph, we seek the way to add the minimum number of chords to a Hamiltonian cycle to get a pancyclic graph with the minimum excess. The authors systematically studied the excess number of pancyclic graphs with small orders up to 37. For general pancyclic graphs, they estimated some upper bounds for the minimum excess.
Chapter 5 deals with unique pancyclicity. A uniquely pancyclic graph (UPC graph for short) is one that contains exactly one cycle of every possible length. There is a negative conjecture by Y. Shi [Discrete Math. 59, 167–180 (1986; Zbl 0589.05046)] on the existence of UPC, which states that there is no UPC graph with \(n\) vertices and \(n+m\) edges for \(m\geq 4\). The case \(m=4\) of the conjecture is proved in this chapter. And all UPC graphs with excess \(m\in \{1, 2, 3\}\) are determined. Some work on UPC graphs from the view of cycle space of a graph are also elaborated. And some bounds on the number of edges in a UPC graph are given.
Chapter 6, Chapter 7 and Chapter 8 treat the counterparts of the concepts and ideas in the former chapters on bipancyclic graphs.
This book does not seem to attempt to cover every aspect of pancyclicity. For example, many sufficient conditions for pancyclicity are not fully discussed. Instead, only several important ones are presented. The choice of contents obviously emphasizes on minimal pancyclicity and unique pancyclicity. It seems appropriate to me, because minimal pancyclicity and unique pancyclicity are two important concepts that have not caught enough attension. The work on these two topics would help to gain more insight into the structure of pancyclic graphs and bipancyclic graphs, and attract more attention of researchers to these concepts.

MSC:

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI