POLYNOMIAL REPRESENTATIONS OF THE BICLIQUE NEIGHBORHOOD OF GRAPHS

Abstract

An induced subgraph $H$ of a graph $G$ is a balanced biclique of $G$ if $H \cong K_{i, i}$ for some $i \in\left\{1,2, \ldots,\left[\frac{|V(G)|}{2}\right]\right\}$. The balanced biclique polynomial of $G$ is given $b(G, x)=\sum_{i=1}^{\frac{\beta(G)}{2}} b_i(G) x^{2 i}$, by where $b_i(G)$ is the number of balanced bicliques of $G$ of order $2 i$ and $\beta(G)$ is the cardinality of a maximum balanced biclique of $G$. The balanced biclique neighborhood polynomial of $G$ which counts the balanced bicliques of $G$ with corresponding neighborhood system cardinality is given by $b n(G ; x, y)=\sum_{j=0}^{n-2} \sum_{i=1}^{\frac{\beta(G)}{2}} b_{i j}(G) x^{2 i} y^j$, where $b_{i j}(G)$ is the number of balanced bicliques of $G$ of order $2 i$ with neighborhood cardinality equal to $j$ and $\beta(G)$ is the cardinality of a maximum balanced biclique of $G$. In this paper, we establish the balanced biclique neighborhood polynomial of some special graphs such as cycle, complete graph, complete bipartite graph, and complete $q$-partite graph.

Received: November 2, 2022;
Accepted: January 2, 2023;