International Journal of Mathematics and Mathematical Sciences
Volume 1 (1978), Issue 2, Pages 177-185
doi:10.1155/S0161171278000216
Graphs which have pancyclic complements
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.
Abstract
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, 3≤n≤p. For a nonnegative integer k, a connected graph G is said to be of rank k if q=p−1+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 p≤pk and Δ(G)<p−2 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.