CLIQUE COMMON NEIGHBORHOOD POLYNOMIAL OF GRAPHS

Abstract

Let $G$ be a simple connected graph of order at least 2 . An $i$-subset of $V(G)$ is a subset of $V(G)$ of cardinality $i$. An $i$-clique is an $i$-subset which induces a complete subgraph of $G$. The clique common neighborhood polynomial of $G$ is given by $\operatorname{ccn}(G ; x, y)=\sum_{j=0}^{n-i} \sum_{i=1}^{\omega(G)} c_{i j}(G) x^i y^j$, where $c_{i j}(G)$ is the number of $i$-cliques in $G$ with common neighborhood cardinality equal to $j$ and $\omega(G)$ is the cardinality of a maximum clique in $G$, called the clique number of $G$. In this paper, we established the clique common neighborhood polynomials of the special graphs such as the complete graph, complete bipartite graph and complete $q$-partite graph. Moreover, we have shown that the clique polynomial is a special evaluation of the clique common neighborhood polynomial at $y=1$.

Received: October 9, 2022
Accepted: November 4, 2022