Test if a graph is vertex pancyclic

savecancel

Let $G$ be a graph of order $n$. A graph $G$ is called pancyclic if it contains a cycle of length $k$ for every $3 ≤ k ≤ n$, and it is called vertex pancyclic if every vertex is contained in a cycle of length $k$ for every $3 ≤ k ≤ n$.

For vertex-pancyclic graphs, we can use a subgraph search approach (as shown below).

def pancyclic(G):
    for a in range(3, G.order() + 1):  # Check for cycles of length 3 to n
        if G.subgraph_search(graphs.CycleGraph(a)) is None:
            return False  # Return False immediately if a cycle of length a is missing
    return True  # Return True if cycles of all lengths are found

However, for vertex-pancyclicity, do we have a better method? The core step is determining whether a given vertex lies on a cycle of given length. Clearly a vertex pancyclic graph is pancyclic. However, the converse is not true. The following is an example since the vertex 6 does not lie any cycle of length 3.

G = Graph([(0, 1), (0, 2), (0, 3), (1, 3), (2, 3),{1,4},{3,4},{3,5},{2,5},{4,6},{5,6}])

Note that if a vertex is in a $k$-cycle, then the vertices on this cycle do not need to be verified again for being in a $k$-cycle, reducing redundant computations.