Common Neighbor Polynomial Of Some Special Trees

M Shikhi, V Anil Kumar


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.


Common neighbor, Common neighbor polynomial, Rooted trees

Full Text:



Eric W. Weisstein, Firecracker Graph, /FirecrackerGraph.html

M. Lepovic, I. Gutman, Some spectral properties of starlike trees, Bulletin T.CXXII de l Academie Serbe des Sciences et des Arts - 2001.

M. Shikhi and V. Anil Kumar, Common neighbor polynomial of graphs, Far East Journal of mathematical sciences,Volume 102, Number 6, 2017, Pages 1201-1221.

Sherif El- Basil, Applications of caterpillar trees in Chemistry and Physics, Journal of Mathematical Chemistry,1987,pages 153-174.



  • There are currently no refbacks.

Copyright (c) 2022 Shikhi M

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Ratio Mathematica - Journal of Mathematics, Statistics, and Applications. ISSN 1592-7415; e-ISSN 2282-8214.