Common Neighbor Polynomial Of Some Special Trees

Abstract

Vertex similarity of nodes is a well studied concept in graph theory as it is highly significant in various fields such as in the study of molecular structure of chemical graphs, measuring consensus rate of different individuals/organizations in network analysis etc. The number of common neighbors shared by two nodes in a network system can be treated as a measure of consensus among the corresponding individuals. This motivates the authors to define the $i$-common neighbor set and the common neighbor polynomial of a graph.

Let $G(V,E)$ be a graph (simple graph) of order $n$ with vertex set $V$ and edge set $E$. Let $(u,v)$ denotes an un ordered vertex pair of distinct vertices of $G$ and let $N(u)$ denote the open neighborhood of the vertex $u$ in $G$. The $i$-common neighbor set of $G$ is defined as $N(G,i):=\{(u,v):u, v\in V, u\neq v \ \text{and}\ |N(u)\cap N(v)|=i\}$, for $0\leq i \leq n-2$. The polynomial $N[G;x]=\sum_{i=0}^{(n-2)} |N(G,i)| x^{i}$ is defined as the common neighbor polynomial of $G$. This polynomial was introduced by the present authors in 2017.

Trees are commonly used to represent hierarchical data structures involved in network file system, possibility spaces, algorithmic routing etc. It is easy to dissect a tree data structure to access the information about a particular part of a huge data. Due to this reason, many researches were conducted to explore the properties of trees. In this paper, we derive the common neighbor polynomial of some special trees like rooted trees, caterpillars etc.