The path graph 
is a tree with two nodes of vertex
degree 1, and the other 
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 
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 
is known as the singleton graph and is equivalent
to the complete graph 
and the star graph 
. 
is isomorphic to the complete bipartite graph 
and 
to 
.
Path graphs 
are graceful.
The path graph 
has chromatic polynomial, independence
polynomial, matching polynomial, and reliability polynomial given by
where 
. These have recurrence equations
The line graph of 
is isomorphic to 
.
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 Graph
Explore with Wolfram|Alpha
References
Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Path Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PathGraph.html