Path Graph
المؤلف:
Gross, J. T. and Yellen, J.
المصدر:
Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.
الجزء والصفحة:
...
11-5-2022
1747
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[![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline4.svg" style="height:21px; width:6px" />"Path", n![<span style=]()
}" 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
where 
. These have recurrence equations
The line graph of 
is isomorphic to 
.
is the Cayley graph of the permutations ![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline43.svg" style="height:21px; width:6px" />![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline44.svg" style="height:21px; width:6px" />2, 1![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline45.svg" style="height:21px; width:6px" />![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline46.svg" style="height:21px; width:6px" />and ![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline47.svg" style="height:21px; width:6px" />![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline48.svg" style="height:21px; width:6px" />1, 3, 2![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/PathGraph/Inline49.svg" style="height:21px; width:6px" />![<span style=]()
}" 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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
