Graph Power

 

The th power of a graph  is a graph with the same set of vertices as  and an edge between two vertices iff there is a path of length at most  between them (Skiena 1990, p. 229). Since a path of length two between vertices  and  exists for every vertex  such that {u,w}" src="https://mathworld.wolfram.com/images/equations/GraphPower/Inline8.svg" style="height:22px; width:46px" /> and {w,v}" src="https://mathworld.wolfram.com/images/equations/GraphPower/Inline9.svg" style="height:22px; width:44px" /> are edges in , the square of the adjacency matrix of  counts the number of such paths. Similarly, the th element of the th power of the adjacency matrix of  gives the number of paths of length  between vertices  and . Graph powers are implemented in the Wolfram Language as GraphPower[g, k].

The graph th power is then defined as the graph whose adjacency matrix given by the sum of the first  powers of the adjacency matrix,

which counts all paths of length up to  (Skiena 1990, p. 230).

Raising any graph to the power of its graph diameter gives a complete graph. The square of any biconnected graph is Hamiltonian (Fleischner 1974, Skiena 1990, p. 231). Mukhopadhyay (1967) has considered "square root graphs," whose square gives a given graph  (Skiena 1990, p. 253).

---

REFERENCES

Fleischner, H. "The Square of Every Two-Connected Graph Is Hamiltonian." J. Combin. Th. Ser. B 16, 29-34, 1974.

Mukhopadhyay, A. "The Square Root of a Graph." J. Combin. Th. 2, 290-295, 1967.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

اخر الاخبار

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

ملاكات العتبة العباسية المقدسة تنهي أعمال غسل صحن مرقد أبي الفضل العباس (عليه السلام)

بمشاركة أمينها العام العتبة العباسية المقدسة تجري أعمال غسل حرم مرقد أبي الفضل العباس (عليه السلام)

قسم الصناعات والحرف الفنية: حققنا الاكتفاء الذاتي في تلبية احتياجات أقسام العتبة العباسية المقدسة

قسم الشؤون الفكرية ينظم ندوة عن الأبعاد الفكرية والعقدية لثورة الإمام الحسين (عليه السلام)

المزيد

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

نصائح عملية للحد من التعرق المفرط في الصيف

أطباء يحذرون: مكمل غذائي شائع قد يدمر الجهاز العصبي

تحذير طبي من تأثير جانبي "غير متوقع" لحقن التخسيس

حمامات الثلج قد تكون خطيرة وأحيانا مميتة.. ما السبب؟

المزيد

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

أكبر جدارية شمسية في العالم تدخل موسوعة غينيس.. مشروع ضخم

تسارع دوران الأرض يثير القلق.. وتحذيرات من "كوارث محتملة" ؟

"سوذبيز" تطرح أكبر قطعة من المريخ على الأرض في مزاد علني

أوبن أيه آي تعتزم إطلاق متصفح إنترنت يعمل بالذكاء الاصطناعي

المزيد

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

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