The path sequence of a graph

Abstract

Let $P(G)=(P_0(G),P_1(G),\cdots ,P_{\ddot{I}}(G))$ be the path sequence of a graph $G$, where $P_i(G)$ is the number of paths with length $i$ and $\ddot{I}$ is the length of a longest path in $G$. In this paper, we first give the path sequences of some graphs and show that the number of paths with length $h$ in a starlike tree is completely determined by its branches of length not more than $h-2$. And then we consider whether the path sequence characterizes a graph from a different point of view and find that any two graphs in some graph families are isomorphic if and only if they have the same path sequence.

20 pages