主題
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 圖

使用 探索

參考文獻

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.

在 上引用

I 圖

請引用為

Weisstein, Eric W. "I 圖。" 來自 Web 資源。 https://mathworld.tw/IGraph.html

學科分類