Theory and Applications of Graphs Theory and Applications of Graphs

Abstract

The (vertex) path-table of a tree 𝑇 contains quantitative information about the paths in 𝑇 . The entry ( 𝑖, 𝑗 ) of this table gives the number of paths of length 𝑗 passing through vertex 𝑣 𝑖 . The path-table is a slight variation of the notion of path layer matrix. In this survey we review some work done on the vertex path-table of a tree and also introduce the edge path-table. We show that in general, any type of path-table of a tree 𝑇 does not determine 𝑇 uniquely. We shall show that in trees, the number of paths passing through edge 𝑥𝑦 can only be expressed in terms of paths passing through vertices 𝑥 and 𝑦 up to a length of 4. In contrast to the vertex path-table, we show that the row of the edge path-table corresponding to the central edge of a tree 𝑇 of odd diameter, is unique in the table. Finally we show that special classes of trees such as caterpillars and restricted thin trees (RTT) are reconstructible from their path-tables.