Path Graph
The path graph P_n is a tree with two nodes of vertex degree 1, and the other n-2 nodes of vertex degree 2. A path graph is therefore a graph that can be drawn so that all of its vertices and edges lie on a single straight line (Gross and Yellen 2006, p. 18).
The path graph of length n is implemented in the Wolfram Language as PathGraph [Range[n]], and precomputed properties of path graphs are available as GraphData [{"Path", n}]. (Note that the Wolfram Language believes cycle graphs to be path graph, a convention that seems neither standard nor useful.)
The path graph P_1 is known as the singleton graph and is equivalent to the complete graph K_1 and the star graph S_1. P_2 is isomorphic to the complete bipartite graph K_(1,1) and P_3 to K_(1,2).
Path graphs P_n are graceful.
The path graph P_n has chromatic polynomial, independence polynomial, matching polynomial, and reliability polynomial given by
where t=sqrt(x^2-4). These have recurrence equations
The line graph of P_n is isomorphic to P_(n-1).
P_2 is the Cayley graph of the permutations {{2, 1}}and {{1, 3, 2}}.
See also
Cycle Graph, Graceful Graph, Hamiltonian Path, Path, Path Complement Graph, Tree, Triangular Snake GraphExplore with Wolfram|Alpha
More things to try:
References
Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.Referenced on Wolfram|Alpha
Path GraphCite this as:
Weisstein, Eric W. "Path Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PathGraph.html