ON CONVEX SUBGRAPH POLYNOMIALS AND SOME OF ITS IMPORTANT VALUES

Abstract

Let $G$ be a connected graph of order $n$. A convex subgraph of $G$ is any subgraph $\langle S\rangle$ induced by a convex subset $S$ of $V(G)$. The convex subgraph polynomial of $G$ is the polynomial $C(G, x)=\sum_{i=0}^n c_i(G) x^i$, where $c_i(G)$ is the number of convex subgraphs of $G$ of order $i$. This study revisits the paper on convex subgraph polynomials discussed in $[6,7,9]$. Specifically, this establishes results relating the convex subgraph polynomial of some $n$th order graph and $(n-1)$ th order and determines the convex subgraph polynomials of the path and cycle as well as their complements. Some values of some graph parameters which are actually values of convex subgraph polynomials at specific points were identified. It is also shown that for every integer $k$, there is a connected graph $G$ for which $C(G,-1)=k$.

Received: October 27, 2023
Accepted: December 21, 2023