تسجيل الدخول

تسجيل

I Graph

المؤلف:  Alspach, B

المصدر:  "The Classification of Hamiltonian Generalized Petersen Graphs." J. Combin. Th. B 34

الجزء والصفحة:  ...

12-4-2022

2646

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.