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 Graph

Explore with Wolfram|Alpha


More things to try:


Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.

Referenced on Wolfram|Alpha

Path Graph

Cite this as:

Weisstein, Eric W. "Path Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications