I Graph

"The"  graph is the path graph on two vertices: .

An -graph  for  and  is a generalization of a generalized Petersen graph and has vertex set

{u_0,u_1,...,u_(n-1),v_0,v_1,...,v_(n-1)} " src="https://mathworld.wolfram.com/images/equations/IGraph/NumberedEquation1.svg" style="height:21px; width:334px" />

and edge set

{u_iu_(i+j),u_iv_i,v_iv_(i+k);i=0,...,n-1}, " src="https://mathworld.wolfram.com/images/equations/IGraph/NumberedEquation2.svg" style="height:23px; width:364px" />

where the subscripts are read modulo  (Bouwer et al. 1988, Žitnik et al. ). Such graphs can be constructed by graph expansion on .

If the restriction  is relaxed to allow  and  to equal ,  gives the ladder rung graph  and  gives the sunlet graph .

Two -graphs  and  are isomorphic iff there exists an integer  relatively prime to  such that either {j_1,k_1}={aj (mod n),ak (mod n)}" src="https://mathworld.wolfram.com/images/equations/IGraph/Inline22.svg" style="height:22px; width:277px" /> or {j_1,k_1}={aj (mod n),-ak (mod n)}" src="https://mathworld.wolfram.com/images/equations/IGraph/Inline23.svg" style="height:22px; width:290px" /> (Boben et al. 2005, Horvat et al. 2012, Žitnik 2012).

The graph  is connected iff . If , then the graph  consists of  copies of  (Žitnik et al. 2012).

The -graph  corresponds to  copies of the graph 

The following table summarizes special named -graphs and classes of named -graphs.

graph
cubical graph
Petersen graph
Dürer graph
Möbius-Kantor graph
dodecahedral graph
Desargues graph
Nauru graph
prism graph
generalized Petersen graph

All -graphs with  have a non-vertex degenerate unit-distance representation in the plane, and with the exception of the families  and , the representations can be constructed with -fold rotational symmetry (Žitnik et al. 2012). While some of these may be vertex-edge degenerate (i.e., an edge passes over a vertex to which it is not incident), computer searching has found only four distinct such cases (, , , and ), and in each case, a different indexing of the I graph gives a unit-distance embedding that is not degenerate in this way (Žitnik et al. 2012).

---

REFERENCES

Alspach, B. "The Classification of Hamiltonian Generalized Petersen Graphs." J. Combin. Th. B 34, 293-312, 1983.

Boben, M.; Pisanski, T.; and Žitnik, A. "I-Graphs and the Corresponding Configurations." J. Combin. Des. 13, 406-424, 2005.

Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; and Star, Z. The Foster Census. Charles Babbage Research Centre, 1988.Frucht, R.; Graver, J. E.; and Watkins, M. E. "The Groups of the Generalized Petersen Graphs." Proc. Cambridge Philos. Soc. 70, 211-218, 1971.

Horvat, B.; Pisanski, T.; and Žitnik, A. "Isomorphism Checking of -Graphs." Graphs Combin. 28, 823-830, 2012.

Lovrečič Saražin, M. "A Note on the Generalized Petersen Graphs That Are Also Cayley Graphs." J. Combin. Th. B 69, 226-229, 1997.

Nedela, R. and Škoviera, M. "Which Generalized Petersen Graphs Are Cayley Graphs?" J. Graph Th. 19, 1-11, 1995.

Petkovšek, M. and Zakrajšek, H. "Enumeration of -Graphs: Burnside Does It Again." To appear in Ars Math. Contemp. 3, 2010.

Steimle, A. and Staton, W. "The Isomorphism Classes of the Generalized Petersen Graphs." Disc. Math. 309, 231-237, 2009.

Žitnik, A.; Horvat, B.; and Pisanski, T. "All Generalized Petersen Graphs are Unit-Distances Graphs." J. Korean Math. Soc. 49, 475-491, 2012.

اخر الاخبار

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

جمعية كشافة الكفيل: المجالس الحسينية تعلّم الفتية قيم نهضة الإمام الحسين (عليه السلام)

عَبرَ المجالس الحسينية.. المجمَع العلمي يقدّم محاضرات دينية وتلاوات قرآنية في بغداد والنجف وميسان

برعاية العتبة العباسية المقدسة.. موكب قناديل السماء يُحيي مراسم اليوم الثالث عشر من المحرّم

بعد انتهاء مراسم ذكرى دفن الأجساد الطاهرة قسم رعاية الصحن يباشر بحملة تنظيف واسعة لصحن مرقد أبي الفضل العباس (عليه السلام)

المزيد

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

اختراق علمي.. دواء يؤخر ظهور السكري من النوع الأول لسنوات

هذا ما يحدث لجسمك إن أهملت نظافة فراشك

لماذا تعتبر النساء أكثر عرضة للإصابة بألزهايمر من الرجال؟

لماذا يحذر الخبراء من الإفراط في تناول الفراولة؟

المزيد

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

السيارات الكهربائية أنظف بنسبة 73% من سيارات الوقود

سيارة لوسِد الكهربائية تدخل "غينيس" بأطول مدى في العالم

نظرية جديدة تنسف كل ما نعرفه عن تشكل أول قارة في الأرض

منذ 37 ألف عام.. دراسة تكشف "أقدم أمراض" أصابت البشر

المزيد

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

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