I Graph
المؤلف:
Alspach, B
المصدر:
"The Classification of Hamiltonian Generalized Petersen Graphs." J. Combin. Th. B 34
الجزء والصفحة:
...
12-4-2022
2219
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
![V(I(n,j,k))=<span style=]() {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
![E(I(n,j,k))=<span style=]() {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 ![<span style=]()
{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 ![<span style=]()
{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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
