George khodkar wallis 2016 minimal pancyclicity

../

small_orders: The chapter's determination of the least excess m(n) of a pancyclic graph on n vertices for all n ≤ 37, by chord-pattern case analysis for at most three chords, two explicit constructions for four and five chords, and the exhaustive search it cites from Griffin for the four-chord bound.

theorem_17: The chapter's one-step bound on the least excess of a pancyclic graph: the least excess on n vertices exceeds the least excess on n − 1 vertices by at most one, with the reverse inequality recorded only as a conjecture.

theorem_19: The chapter's general upper bounds on the least excess of a pancyclic graph: Theorem 18, excess j + 2 for 2^j + 21 ≤ n ≤ 2^{j+1} + 20 and j ≤ 21, and Theorem 19, excess at most 2^h + 2h on the window 2^{2^h+h+1} + 2^h + h + 2 ≤ n ≤ 2^{2^h+h+2} + 2^h + h + 1, both by explicit chord constructions.

---

John C. George, Abdollah Khodkar and W. D. Wallis, Pancyclic and Bipancyclic Graphs, SpringerBriefs in Mathematics, Springer International Publishing, 2016, xii+108 pp.; ISSN 2191-8198, ISBN 978-3-319-31950-6, eBook ISBN 978-3-319-31951-3, DOI 10.1007/978-3-319-31951-3, Library of Congress Control Number 2016935702, "© The Author(s) 2016" (copyright page, PDF p. 5); the authors at Gordon State College, the University of West Georgia and Southern Illinois University. The work filed here is its Chapter 4, Minimal Pancyclicity, printed pp. 35--47, whose footer prints "J.C. George et al., Pancyclic and Bipancyclic Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-3-319-31951-3_4" (p. 35). Cited as [GKW16] on the problem page. The preface (p. vii) dates the subject to Bondy's 1971 introduction of pancyclic graphs and thanks, among others, Alison Marr, a coauthor of the chapter's source [13]. The chapter's sources, from the book's reference list (pp. 107--108): [3] Bondy, Pancyclic graphs I, J. Comb. Theory (B) 11 (1971), 80--84, filed as bondy_1971_pancyclic_graphs_i; [13] George, Marr and Wallis, Minimal pancyclic graphs, J. Comb. Math. Combin. Comput. 86 (2013), 125--133 (not held; the paper Griffin cites as a preprint); [16] Griffin, Minimal pancyclicity, listed as "(to appear)" with no journal named, filed from arXiv as griffin_2013_minimal_pancyclicity; [23] Markström, A note on uniquely pancyclic graphs, Australas. J. Combin. 44 (2009), 105--110; [30] Shi, Some theorems of uniquely pancyclic graphs, Discrete Math. 59 (1986), 167--180; [32] Sridharan, On an extremal problem concerning pancyclic graphs, J. Math. Phys. Sci. 12 (1978), 297--306; none of the last three held. The reference list also carries [31] Shi, The number of cycles in a Hamilton graph, Discrete Math. 133 (1994), 249--257, the problem page's [Sh94], which the chapter does not cite.

The copy read for this card is the publisher's production PDF of the whole eBook, obtained as one volume on 2026-09-22 (the chapter is not supplied separately): 117 pages, the unnumbered cover and the front matter (pp. i--xii) on PDF pp. 1--13 and the body from PDF p. 14 (printed p. 1; the preface is p. vii = PDF p. 8, the copyright page PDF p. 5); the eBook omits the blank versos before chapters, so the offset changes at each chapter, and within Chapter 4 printed p. $n$ is PDF p. $n+12$ (pp. 35--47 = PDF pp. 47--59); the reference list is printed pp. 107--108 = PDF pp. 116--117. Typeset from InDesign (Adobe PDF Library 10.0.1 per the file's metadata, created 27 April 2016, modified 13 May 2016), with a text layer that reads the prose cleanly and drops the minus signs, inequality signs, binomial coefficients and the stars on the chord labels $A_k^*$ of the displays. That edition is the version of record; no preprint or repository version is known. Provenance: obtained from the publisher on 2026-09-22 as a DRM-free production PDF, from https://doi.org/10.1007/978-3-319-31951-3_4 (the chapter's DOI, resolving to the publisher's chapter page, from which the volume was obtained); 3,078,283 bytes. The file prints "© The Author(s) 2016" and "This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned" on the volume's copyright page (PDF p. 5), every other right reserved.

Read status: claims checked for the definitions of $m(n)$, excess and minimal pancyclic graph, Conjecture 4.1, the bound (4.1) and the vertex insertion behind Theorem 17 (p. 35), Theorem 17 and the chord vocabulary (p. 36), the one- and two-chord values (p. 37), the four- and five-chord conclusions and the sentence citing Griffin's exhaustive search (p. 42), the critique of Sridharan (pp. 42--43) and the graphs $S_n^k$ (p. 43), the chord $A_4^*$ and the excess-5 and excess-6 ranges (p. 44), the definitions of $x_k$, $A_k$, $A_k^*$ and $G_k$ (p. 45), the excess table, Theorem 18 and the excess-6 argument (p. 46), and the second table, the general recipe and Theorem 19 (p. 47), each read clause by clause on the page images of PDF pp. 47--49 and 54--59 on 2026-09-22; the copyright page (PDF p. 5) was read on the page image for the citation. The nine-vertex argument (p. 38), the three-chord table and case analysis (pp. 39--40), the four-chord cycle table (p. 41) and the five-chord cycle table (p. 42) were read in the text layer for structure only, and none of their cycle lists was checked; the seventeen-vertex cycle list (p. 44) was read on the page image but not checked. The constructions behind Theorems 18 and 19 were followed at the level stated on theorem_19. Chapters 1--3 and 5--8 were not read beyond the table of contents, the opening of Chapter 3 (p. 21) and its open problems (p. 34), read in the text layer to confirm that no other part of the book states a bound on $m(n)$. Nothing here is independently reviewed.

Contents

• § 4.1, Introduction (p. 35, page image). For each $n\ge3$ the chapter defines $m(n)$ as the largest integer such that every pancyclic graph on $n$ vertices has at least $n+m(n)$ edges (equivalently, the minimum of $e(G)-n$ over pancyclic $G$ on $n$ vertices), and calls a pancyclic graph on $n$ vertices with exactly $n+m(n)$ edges minimal. Quoted definition: "The difference $e(G)-v(G)$ is called the excess of the graph $G$, so $m(n)$ is the minimum excess for an $n$-vertex pancyclic graph." The chapter's $m(n)$ is therefore the problem's $h(n)$, and differs from Griffin's $m(n)$, the edge count, by $n$. The chapter attributes the notion of minimal pancyclicity to Bondy's paper [3], the one that defined pancyclic graphs, and credits Bondy with the question, quoted there, "What is the minimum number of edges in a pancyclic graph" on a given number of vertices. Conjecture 4.1 (quoted): "$m(n)\ge m(n-1)$", called a popular conjecture. Display (4.1), from Corollary 12.3 of Chapter 3: $m(n)\le\frac{n^2-3n}2+3$. A new vertex joined to both ends of a Hamilton-cycle edge of a minimal pancyclic graph on $n-1$ vertices, that edge kept, gives Theorem 17 (p. 36, quoted): "$m(n)\le m(n-1)+1$"; the chapter notes that under Conjecture 4.1 this leaves $m(n)\in\{m(n-1),m(n-1)+1\}$. Theorem 17 is Griffin's Proposition 2 and Conjecture 4.1 is Griffin's Conjecture 1, each in the other's letters.
• § 4.2, Minimal Pancyclic Graphs: Small Orders (pp. 36--41). The section opens by crediting its results to [13, 16] and announcing the value of $m(n)$ for every $n\le37$. A pancyclic graph is drawn as its Hamilton cycle $(a_1,\ldots,a_n,a_1)$ with chords; a chord of deficiency $d$ (the number of bypassed vertices) yields cycles of lengths $d+2$ and $n-d$; two chords intersect or enclose, pairs of chords are of type A (disjoint, not crossing), B (a common endpoint) or C (crossing, "skew"). § 4.2.1 (p. 37, quoted): "$m(n)=0$ if and only if $n=3$, and $m(n)=1$ if and only if $n=4$ or 5". § 4.2.2: two chords give at most seven cycles; the nine-vertex case is excluded by citing Shi [30], giving (p. 37, quoted) "$m(n)=2$ if and only if $6\le n\le8$", with a direct segment-length argument for $n=9$ on p. 38 ending "Therefore $m(9)=3$". § 4.2.3: the fourteen three-chord configurations (Fig. 4.4) and a table of their cycle counts, at most 15 (type CCC); examples with three chords for $10\le n\le14$; type CCC has no 3-cycle, BCC's fifteen-vertex case would have to be uniquely pancyclic, which [23] excludes, and a segment-length case analysis of type ACC concludes (p. 40) that both $n=15$ and $n=16$ need at least four chords. Fig. 4.5 (p. 41) draws minimal pancyclic graphs up to order 14.
• § 4.3, Four Chords (pp. 41--42). Fig. 4.6, a graph on $x+13$ vertices with four chords, and a table of the cycle lengths it contains, which cover every length from 3 to $n$ for $1\le x\le10$; hence $m(n)=4$ for $15\le n\le24$ (p. 42). The lower bound beyond that range is cited, not proved (p. 42, quoted): "It is reported in [16] that an exhaustive search was conducted that shows there is no pancyclic graph on 25 or more vertices with four or fewer chords", and the section closes by recording $m(n)$ as established for all $n\le24$.
• § 4.4, Five Chords (pp. 42--43). Fig. 4.7, a graph on $n=x+21$ vertices with five chords, and its cycle-length table, lengths 3--19 and $n$ down to $n-17$: "This proves that $m(n)=5$ for $25\le n\le37$" (p. 42). The lower half of that equality is the four-chord exclusion cited from [16]. Paged with §§ 4.2--4.3 on small_orders.
• § 4.5, More General Bounds for Pancyclics (pp. 42--47, page images). Sridharan [32] is described as claiming the value of $m(n)$ for every order, and the chapter's critique (pp. 42--43, quoted) is that "it appears that the author assumed Conjecture 4.1 to fill in the gaps" left by omitted orders, and that "it is never proven that the graphs constructed are minimal"; Bondy's Mathematical Reviews review of that paper is quoted. Sridharan's graphs $S_n^k$ carry chords $A_0,\ldots,A_k$ of deficiencies $1,2,4,\ldots,2^k$, pairwise non-intersecting and non-enclosing, giving cycles of lengths $2^i+2$ and $n-j$ for $j$ a sum of distinct deficiencies, which the chapter says suffices for pancyclicity when $n-(2^{k+1}-1)\le5$ (p. 43); the chapter's computer analysis finds Sridharan's construction non-pancyclic at $n=17$ (no 5-cycle; the full cycle list is printed, p. 44) and at all of $54\le n\le68$ except 60 and 65 (a table of the missing lengths, p. 45), because for $n<69$ the chord of deficiency $2^5$ intersects or encloses earlier chords. The chapter then modifies Sridharan's construction slightly (p. 45): vertices $x_0=a_1$, $x_k=a_{2^k+k}$; chords $A_k=(x_k,x_{k+1})$ of deficiency $2^k$, each opening at the previous chord's closing vertex, defined when $n>2^{k+1}+k$; and $A_k^*=(x_k,x_0)$ of deficiency $n-2^k-k$. With $A_0,\ldots,A_{k-1}$ the graph has cycles of lengths $n-d$ for $1\le d\le2^k-1$, $n$, and $2^i+2$ for $i<k$; adding $A_k^*$ gives $n-2^k-k+2$, $2^k+k$ and, for $k>1$, every length from $k+1$ to $2^k+k-1$. $G_k=H_n\cup A_0\cup\cdots\cup A_{k-1}\cup A_k^*$ for $2^k+k+1\le n\le2^{k+1}+k$, and $H_n\cup A_0\cup\cdots\cup A_{k-1}\cup A_k$ for $n\ge2^{k+1}+k+1$, is pancyclic for $2\le k\le4$ on the orders of the table of p. 46, which records excess $k+1$ for $G_k$: excess 3 for $9\le n\le12$, 4 for $13\le n\le20$, 5 for $21\le n\le36$ (the chapter notes that $G_4$ fails to be pancyclic at $n=37$, the largest case). Adding both $A_4$ and $A_4^*$ gives excess 6 for $37\le n\le52$, and, for $5\le j\le20$, $G_j\cup A_4^*$, excess $j+2$, is pancyclic for $2^j+j+1\le n\le2^{j+1}+20$ while the chords do not overlap, whence Theorem 18 (p. 46, quoted): "When $j\le21$, there is a pancyclic graph on $n$ vertices with $n+j+2$ edges whenever $2^j+21\le n\le2^{j+1}+20$." "So we have a bound for all orders up to $n=2^{22}+20=4{,}194{,}234$ [sic]" (p. 46; a filing observation, not a review verdict: $2^{22}+20$ is $4{,}194{,}324$). A second table (p. 47) lists excess 6 for $37\le n\le52$ through excess 12 for $1045\le n\le2068$. For $j=22$ the 21-cycle is missing and the chord $A_5^*$ supplies every length from 6 to 37; in general $A_j^*$ with $A_0,\ldots,A_{j-1}$ gives all lengths from $j+1$ to $2^j+j$, and the chapter's recipe adds $A_{h+1}^*$, to supply the cycle of length $2^h+h+1$, once $n>2^j+j+1$ with $j=2^h+h+1$, so on the stated window the chords $A_0,\ldots,A_{2^h+h+1}$ and $A_4^*,\ldots,A_{h+1}^*$ give a pancyclic graph. Theorem 19 (p. 47, quoted): "When $2^{(2^h+h+1)}+2^h+h+2\le n\le2^{(2^h+h+2)}+2^h+h+1$, there is a pancyclic graph on $n$ vertices with $n+2^h+2h$ edges. So the excess for a minimal pancyclic graph with $n$ as stated is at most $2^h+2h$." This is the chapter's last sentence; it states no lower bound for general $n$, no logarithmic form of any bound, and does not mention the bounds of p. 84 of [3]. A filing observation, not a review verdict: neither theorem states a lower bound on its parameter, and each fails for its smallest values against the values of $m(n)$ the chapter itself records on pp. 37--42 (those for $25\le n\le37$ resting on Griffin's search). Theorem 18 at $j=0$ (excess 2 at $n=22$), $j=1$ (excess 3 at $n=23$, 24) and $j=2$ (excess 4 for $25\le n\le28$) contradicts $m(n)=4$ for $15\le n\le24$ and $m(n)=5$ for $25\le n\le37$; two or three chords give at most 7 or 15 cycles, fewer than the $n-2$ lengths needed. The argument before the theorem is stated for $5\le j\le20$, and the cases $j=3$ and $j=4$ are the graphs $G_4$ and the excess-6 graph. At $j=21$ the same chords ($A_0,\ldots,A_{20}$, $A_{21}^*$ and $A_4^*$) give a 21-cycle only at $n=2^{21}+23$ and $n=2^{21}+40$, so on the rest of the theorem's last window, $2^{21}+21\le n\le2^{22}+20$, the printed construction does not give excess 23. Theorem 19 at $h=0$ (excess 1 for $7\le n\le10$) contradicts $m(n)\ge2$ for $n\ge6$, and at $h=1$ (excess 4 for $21\le n\le36$) contradicts $m(n)=5$ for $25\le n\le36$ and falls below the excess 5 of the chapter's own table (p. 46); in both cases the listed chords ($A_0,\ldots,A_2$ and $A_0,\ldots,A_4$, three and five chords) do not number $2^h+2h$, because that count adds the $h-2$ starred chords $A_4^*,\ldots,A_{h+1}^*$ and so presupposes $h\ge2$. At $h=2$ ($136\le n\le263$, excess 8) the last listed chord $A_7$ is defined only for $n>263$ and no starred chord is listed, so with $A_7^*$ in its place the eight chords give every length from 8 to $n$ and 3, 4, 6, but no 5-cycle unless $n=138$ and no 7-cycle unless $n=140$ (the short cycle of $A_7^*$ has length $n-133$), so never both; whether excess 8 suffices there is not settled by the chapter, whose Theorem 18 gives 8 for $n\le148$ and 9 for $149\le n\le263$. From $h=3$ on, with $A_j^*$ in place of the likewise undefined $A_j$, $j=2^h+h+1$, the listed chords do give a pancyclic graph, checked at both ends of the $h=3$ window. Read on the page images of PDF pp. 57--59 (printed pp. 45--47) and checked by a short cycle-length computation for the small cases, not retained, on 2026-09-22; the $j=21$ and $h=2$ counts were checked the same way, not retained, on 2026-10-07. Paged on theorem_19.

Compiled scope

The chapter is compiled at statement depth for the two passages Problem 1016 consumes: the general upper bounds, Theorems 18 and 19 (pp. 46--47), read on the page images with their constructions followed and paged on theorem_19, and the values of $m(n)$ for $n\le37$ (pp. 37--42), read on the page images at their concluding sentences with the case analyses read for structure only and paged on small_orders. Theorem 17 and Conjecture 4.1 (pp. 35--36) are read on the page images, with the construction behind Theorem 17, and paged on theorem_17. The rest of the book is outside the compiled scope. Nothing here is independently reviewed.

Bears on. #1016: the chapter's $m(n)$, the minimum excess of a pancyclic graph on $n$ vertices (p. 35), is the problem's $h(n)$ exactly. Its Sections 4.2--4.4 establish $h(n)$ for $n\le37$ ("$m(n)=0$ if and only if $n=3$", p. 37, through "$m(n)=5$ for $25\le n\le37$", p. 42), the values of Griffin's Table 1, with the four-chord exclusion for $n\ge25$ cited from Griffin's exhaustive search. Its Section 4.5 is the passage the site names for "the first published proof of the upper bound" $h(n)\le\log_2n+\log_*n+O(1)$: its general results are Theorem 18 (p. 46), excess at most $j+2$ for $2^j+21\le n\le2^{j+1}+20$ and $j\le21$, that is $h(n)\le\log_2n+2$ for $53\le n\le2^{22}+20$, and Theorem 19 (p. 47), excess at most $2^h+2h$ for $2^{(2^h+h+1)}+2^h+h+2\le n\le2^{(2^h+h+2)}+2^h+h+1$. A filing observation, not a review verdict: on Theorem 19's window $j=2^h+h+1<\log_2n<j+2$, so its bound $2^h+2h=j+h-1$ reads $h(n)<\log_2n+h$ with $h<\log_2\log_2n$, the form $\log_2n+\log_2\log_2n+O(1)$ the problem's thread reports from Jia 1996, and the theorem is stated only on those windows, which for successive $h$ leave $n$ between $2^{(2^h+h+2)}+2^h+h+1$ and $2^{(2^{h+1}+h+2)}+2^{h+1}+h+3$ uncovered (for $h\ge4$, beyond the reach of Theorem 18); the preceding sentence describes the chord recipe for a general $j$ but the theorem does not state it. The chapter prints no bound of the form $\log_2n+\log_*n+O(1)$ and does not restate or cite the bounds Bondy claimed on p. 84 of the 1971 paper, so the chapter does not, on the reading here, supply a proof of the upper bound in the site's form; what it proves is recorded on the result page. The chapter also lists Griffin's preprint as "(to appear)" in 2016 and gives the George--Marr--Wallis values paper a journal reference. Theorem 17, $h(n)\le h(n-1)+1$ (theorem_17), and Conjecture 4.1, $h(n)\ge h(n-1)$, left open, are Griffin's Proposition 2 and Conjecture 1, which Griffin states for the edge count $n+h(n)$. The problem page reads Theorems 18 and 19 on the page images at statement depth with their constructions followed.

Results.

• Small orders (pp. 37--42): $m(n)=0$ for $n=3$, $1$ for $4\le n\le5$, $2$ for $6\le n\le8$, $3$ for $9\le n\le14$, $4$ for $15\le n\le24$ and $5$ for $25\le n\le37$, from case analysis, the constructions of Figs. 4.6 and 4.7, and the exhaustive search cited from Griffin.
• Theorems 18 and 19 (pp. 46--47): pancyclic graphs with excess $j+2$ for $2^j+21\le n\le2^{j+1}+20$, $j\le21$, and with excess $2^h+2h$ for $2^{(2^h+h+1)}+2^h+h+2\le n\le2^{(2^h+h+2)}+2^h+h+1$, by the chords $A_k$ and $A_k^*$ of p. 45.
• Theorem 17 (p. 36): $m(n)\le m(n-1)+1$, by joining a new vertex to both ends of a Hamilton-cycle edge (p. 35); with Conjecture 4.1 (p. 35), $m(n)\ge m(n-1)$, stated as a popular conjecture.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.