TOPICS
Search

I Graph


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

An I-graph I(n,j,k) for 1<=j,k<n and j,k!=n/2 is a generalization of a generalized Petersen graph and has vertex set

 V(I(n,j,k))={u_0,u_1,...,u_(n-1),v_0,v_1,...,v_(n-1)}

and edge set

 E(I(n,j,k))={u_iu_(i+j),u_iv_i,v_iv_(i+k);i=0,...,n-1},

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

If the restriction j,k<n is relaxed to allow j and k to equal n, I(n,n,n) gives the ladder rung graph nP_2 and I(n,1,n) gives the sunlet graph C_n circledot K_1.

Two I-graphs I(n,j,k) and I(n,j_1,k_1) are isomorphic iff there exists an integer a relatively prime to n such that either {j_1,k_1}={aj (mod n),ak (mod n)} or {j_1,k_1}={aj (mod n),-ak (mod n)} (Boben et al. 2005, Horvat et al. 2012, Žitnik 2012).

The graph I(n,j,k) is connected iff gcd(n,j,k)=1. If gcd(n,j,k)=d>1, then the graph I(n,j,k) consists of d copies of I(n/d,j/d,k/d) (Žitnik et al. 2012).

The I-graph (rn,rj,rk) corresponds to r copies of the graph I(n,j,k)

IGraphs

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

All I-graphs with n>=3 have a non-vertex degenerate unit-distance representation in the plane, and with the exception of the families I(n,j,j) and I(12m,m,5m), the representations can be constructed with n-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 (I(9,2,4), I(12,2,5), I(30,5,9), and I(30,9,14)), 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).


See also

Generalized Petersen Graph, Graph Expansion, H Graph, Knödel Graph, Ladder Rung Graph, Sunlet Graph,Unit-Distance Graph, Y Graph

Explore with Wolfram|Alpha

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 I-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 I-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.

Referenced on Wolfram|Alpha

I Graph

Cite this as:

Weisstein, Eric W. "I Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IGraph.html

Subject classifications