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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

العتبة العباسية المقدسة تختتم فعاليات حفل التكليف المركزي الثامن بمشاركة أكثر من 6 آلاف تلميذة

من الخيام إلى الفتوى.. عرض مسرحي ضمن فعاليات اليوم الثاني لحفل التكليف

ضمن فعاليات اليوم الثاني من حفل التكليف المركزي الثامن تلميذات مدارس كربلاء يرددن نشيد التكليف

عرض فيلم عن مشروع الورود الفاطمية ضمن فعاليات اليوم الثاني من حفل التكليف المركزي الثامن

المزيد

الآخبار الصحية

عوامل تضعف القدرات الإدراكية لدى الإنسان

طريقة جديدة لتجديد خلايا الدماغ

دراسة بريطانية: الأطعمة النباتية عالية الجودة تقلل خطر فشل القلب

7 أطعمة يومية "تسمم" جسمك بالبلاستيك دون أن تشعر

المزيد

الآخبار التكنلوجية

اكتشاف أثري في أوريغون الأمريكية قد يعيد كتابة تاريخ البشرية

اكتشاف كائن بحري مدرع بلسان "حديدي" في بحر اليابان

نظام كوكبي "مقلوب" يحير علماء الفلك

بسبب الذكاء الاصطناعي.. هذه الوظائف "ستختفي" بعد أشهر قليلة ؟!

المزيد

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

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