Path Graph (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
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.House of Graphs. Path Graphs. P2,P3, P4,P5, P6,P7, P8, ....
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Path Graph." FromMathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PathGraph.html