WEAKLY PANCYCLIC POLYNOMIAL OF A GRAPH

Abstract

Let $G$ be a graph. For $i=g(G), g(G)+1, \ldots, c(G)$, where $g(G)$ is the length of shortest cycle in $G$ and $c(G)$ is the length of longest cycle in $G$, we say that $G$ is a weakly pancyclic graph if it contains cycles of every length from $g(G)$ to $c(G)$. The weakly pancyclic polynomial of $G$ is defined by
$$
W(G, x)=\sum_{g(G)}^{c(G)} y_i(G) x^i,
$$
where $y_i(G)$ is the number of weakly pancyclic subgraphs of $G$ with order $j$. This study presents explicit formulations for the weakly pancyclic polynomial of specific graphs including complete graph $K_n$, complete bipartite graph $K_{m, n}$ and graphs of the form $G+K_1$.

Specifically, it explores the fan $F_n$, and wheel $W_n$. Additionally, the study furnishes a characterization of weakly pancyclic graphs and establishes a lower bound on the coefficients of the polynomial for $P_m \times P_n$.

Received: January 16, 2024
Revised: February 12, 2024
Accepted: February 21, 2024