Higher order invariants of a graph based on the path sequence

Abstract

Let $G=(V,E)$ be a simple and connected graph. A $h$-order invariant of $G$ based on the path sequence is defined from a set of real numbers $f(x_0,x_1,\cdots ,x_h)$ as ${}^h{I}_f(G)=\sum _{v_0{v}_1{v}_2\cdots v_h}f\left(d_0,d_1,\cdots ,d_h\right)$, where the sum runs over all paths $v_0{v}_1{v}_2\cdots v_h$ of length $h$ and $d_i$ is the degree of vertex $v_i$ in $G$. In this paper, we first show that the $h$-order invariant of a starlike tree $S_n$ can be determined completely by its branches whose length does not exceed $h$. And then we find conditions on the function $f$ for some graph families $\mathcal{G}$ such that any graph $G\in \mathcal{G}$ can be determined by the higher order invariants ${}^h{I}_f(G)$ for $0⩽h⩽\ddot{I}$, where $\ddot{I}$ is the length of a longest path in $G$.

23 pages