International Journal of Mathematics and Mathematical Sciences
Volume 1 (1978), Issue 2, Pages 177-185

Graphs which have pancyclic complements

H. Joseph Straight

Department of Mathematics, SUNY College at Fredonla, Fredonla 14063, New York, USA

Received 23 January 1978; Revised 1 March 1978

Copyright © 1978 H. Joseph Straight. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Let p and q denote the number of vertices and edges of a graph G, respectively. Let Δ(G) denote the maximum degree of G, and G¯ the complement of G. A graph G of order p is said to be pancyclic if G contains a cycle of each length n, 3np. For a nonnegative integer k, a connected graph G is said to be of rank k if q=p1+k. (For k equal to 0 and 1 these graphs are called trees and unicyclic graphs, respectively.)

In 1975, I posed the following problem: Given k, find the smallest positive integer pk, if it exists, such that whenever G is a rank k graph of order ppk and Δ(G)<p2 then G¯ is pancyclic. In this paper it is shown that a result by Schmeichel and Hakiml (2) guarantees that pk exists. It is further shown that for k=0, 1, and 2, pk=5, 6, and 7, respectively.