COMBINATORIAL APPROACH IN COUNTING THE NEIGHBORS OF CLIQUES IN A GRAPH

Abstract

Let $G$ be a simple connected graph. Then 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 neighborhood polynomial of $G$ is given by $c n(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 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 obtain the clique neighborhood polynomials of the special graphs such as the complete graph, complete bipartite graph and complete $q$-partite graph using combinatorial approach.

Received: September 14, 2023
Accepted: October 9, 2023