GRAPHS WHICH HAVE PANCYCLIC COMPLEMENTS

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 p_k, if it exists, such that whenever G is a rank k graph of order p ≤ P_k and Δ(G) ＜ p - 2 then G is pancyclic. In this paper it is shown that a result by Schmeichel and Hakiml (2) guarantees that P_k exists. It is further shown that for k = 0, 1, and 2, P_k = 5, 6, and 7, respectively.

並列關鍵字

Graph ； pancyclic graphs ； uniclic graphs

國際替代計量

全文下載

主題瀏覽