主题
Search

I 图


“The” I 图是两个顶点的 路径图P_2

I-图 I(n,j,k) 对于 1<=j,k<nj,k!=n/2广义彼得森图的推广,并且具有顶点集

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

和边集

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

其中下标以 n 为模读取(Bouwer et al. 1988, Žitnik et al. )。这样的图可以通过 图扩展P_2 上构造。

如果限制 j,k<n 放宽到允许 jk 等于 nI(n,n,n) 给出 梯子横档图 nP_2,而 I(n,1,n) 给出 太阳花图 C_n circledot K_1

两个 I-图 I(n,j,k)I(n,j_1,k_1) 是同构的 当且仅当 存在一个整数 an 互质,使得 {j_1,k_1}={aj (mod n),ak (mod n)}{j_1,k_1}={aj (mod n),-ak (mod n)} (Boben et al. 2005, Horvat et al. 2012, Žitnik 2012)。

I(n,j,k)连通的 当且仅当 gcd(n,j,k)=1。如果 gcd(n,j,k)=d>1,则图 I(n,j,k)dI(n/d,j/d,k/d) 的副本组成 (Žitnik et al. 2012)。

I-图 (rn,rj,rk) 对应于 r 个图 I(n,j,k) 的副本

IGraphs

下表总结了特殊的命名 I-图和命名 I-图的类。

所有 I-图,其中 n>=3 在平面上都具有非顶点退化的单位距离表示,并且除了族 I(n,j,j)I(12m,m,5m) 之外,这些表示可以用 n 重旋转对称性来构造 (Žitnik et al. 2012)。虽然其中一些可能是顶点-边退化的(即,一条边越过了一个它不相关的顶点),但计算机搜索只发现了四个不同的此类情况(I(9,2,4)I(12,2,5)I(30,5,9)I(30,9,14)),并且在每种情况下,I 图的不同索引都给出了在这种意义上非退化的单位距离嵌入 (Žitnik et al. 2012)。


另请参阅

广义彼得森图, 图扩展, H 图, 克诺德尔图, 梯子横档图, 太阳花图,单位距离图, Y 图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上引用

I 图

请引用为

Weisstein, Eric W. "I 图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/IGraph.html

学科分类