Path Graph

 

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[{" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline4.svg" style="height:21px; width:6px" />"Path", n}" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline5.svg" style="height:21px; width:6px" />]. (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

			(1)
			(2)
			(3)
			(4)

where . These have recurrence equations

			(5)
			(6)
			(7)
			(8)

The line graph of  is isomorphic to .

 is the Cayley graph of the permutations {" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline43.svg" style="height:21px; width:6px" />{" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline44.svg" style="height:21px; width:6px" />2, 1}" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline45.svg" style="height:21px; width:6px" />}" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline46.svg" style="height:21px; width:6px" />and {" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline47.svg" style="height:21px; width:6px" />{" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline48.svg" style="height:21px; width:6px" />1, 3, 2}" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline49.svg" style="height:21px; width:6px" />}" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline50.svg" style="height:21px; width:6px" />.

---

REFERENCES

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

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength