King Graph

 

The  king graph is a graph with  vertices in which each vertex represents a square in an  chessboard, and each edge corresponds to a legal move by a king.

The number of edges in the  king graph is , so for , 2, ..., the first few values are 0, 6, 20, 42, 72, 110, ... (OEIS A002943).

The order  graph has chromatic number  for  and  for . For , 3, ..., the edge chromatic numbers are 3, 8, 8, 8, 8, ....

King graphs are implemented in the Wolfram Language as GraphData[{" src="https://mathworld.wolfram.com/images/equations/KingGraph/Inline13.svg" style="height:22px; width:6px" />"King", {" src="https://mathworld.wolfram.com/images/equations/KingGraph/Inline14.svg" style="height:22px; width:6px" />m, n}" src="https://mathworld.wolfram.com/images/equations/KingGraph/Inline15.svg" style="height:22px; width:6px" />}" src="https://mathworld.wolfram.com/images/equations/KingGraph/Inline16.svg" style="height:22px; width:6px" />].

All king graphs are Hamiltonian and biconnected. The only regular king graph is the -king graph, which is isomorphic to the tetrahedral graph . The -king graphs are planar only for  (with the  case corresponding to path graphs) and , some embeddings of which are illustrated above.

The -king graph is perfect iff  (S. Wagon, pers. comm., Feb. 22, 2013).

Closed formulas for the numbers  of -cycles of  with  are given by

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

where the formula for  appears in Perepechko and Voropaev.

The numbers of Hamiltonian cycles for the -king graphs for , 3, ... are 6, 32, 5660, 4924128, ... (OEIS A140521), with the corresponding numbers of Hamiltonian paths given by 24, 784, 343184, ... (OEIS A158651).

---

REFERENCES

Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.

Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."

Sloane, N. J. A. Sequences A002943, A140521, and A158651 in "The On-Line Encyclopedia of Integer Sequences."

اخر الاخبار

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

المجمع العلمي يواصل إقامة مسابقة الثقلين القرآنية لطلبة مدارس كربلاء

عضو مجلس إدارة العتبة العباسية المقدسة يطلع على آليات تطوير البرامج التعليمية في مجموعة العميد

مجموعة مناحل الكفيل تختتم مشاركتها في معرض السليمانية الدولي للزراعة والصناعات الغذائية

لتوثيق التراث العلمي.. وفد قسم شؤون المعارف يلتقي عددًا من أعلام مدينة النجف

المزيد

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

ثورة طبية.. الذكاء الاصطناعي يكشف سرطان الكلى في وقت قياسي

لتعزيز الطاقة والتغلب على التعب.. عليك بـ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