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.

اخر الاخبار

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

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

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

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

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

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

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

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