一般化蜂窩環輪面的，「通過每點的二部泛圈性」及「通過每邊的二部泛圈性」

Vertex-Bipancyclicity and Edge-Bipancyclicity of the Generalized Honeycomb Tori

吳依蒨(Yi-Chien Wu)

指導教授 ： 高欣欣

中原大學/理學院/應用數學系/碩士(2007年)

https://doi.org/10.6840/cycu200700201

摘要

設 $m$, $n$ 和 $s$ 為整數, $mge 2$、 $nge 4$、 $0le sle n$ 且 $m+n$
為偶數。在平行和分散式的網際網路中,有一smallskip 種名為一般化蜂窩環輪面(it{Generalized Honeycomb Tori GHT$(m,n,s)$}$)$
的圖形被廣泛應用。一個二部圖smallskip $G$ 包含從 extup{4} 到所有頂點數大小的所有偶數圈圈,則我們稱此圖 $G$ 是
「偶泛圈圖」。如果一個二部圖 $G$ 被稱作smallskip 「點-偶泛圈圖」 $($或「邊-偶泛圈圖」$)$ 表示此圖非但有 extup{4}
到所有頂點數大小的偶數圈圈外,對於所有的點 $($或邊$)$ smallskip 都要有過此點 $($或邊$)$ 從 extup{4}
到所有頂點數大小的所有偶數圈圈。在本篇文章中,我們研究出一般化蜂窩環輪面是smallskip extup{10}-偶泛圈且包含大小為
extup{6} 的圈圈,而某些特殊的案例則是偶泛圈或 extup{6}-偶泛圈。因為 GHT$(m,n,s)$ 中的點和smallskip
邊都會存在在一個六角形上,且我們在建構絕大部分的圖的所有大小的圈圈,除了在 $n=4$ 時的 $C_4$ 和 $n=8$ 時的 $C_8$ 外
,時我們都利用六角形去組成,這意味著對於任意一般化蜂窩環輪面的點 $($或邊$)$ 都會被一個長度為 smallskip$l$ 的圈圈所經過,此處的
$l$ 為大於等於 extup{6}的偶數。也就是說,在某些特殊案例一般化蜂窩環輪面是點-偶泛圈和smallskip
邊-偶泛圈。所證明的結果已經是最佳化的了。 }

關鍵字

蜂窩環輪面 ； 偶泛圈 ； 點-偶泛圈 ； 邊-偶泛圈

並列摘要

Assume that $m,n$ and $s$ are integers with $mge 2, n ge 4, 0le s

並列關鍵字

vertex-bipancyclic ； bipancyclic ； Honeycomb torus ； edge-bipancyclic

參考文獻

[1] B. Alspach, D. Hare, “Edge-Pancyclic Block-Intersection Graphs”, Discrete Math-ematics, vol. 97, pp. 17–24, 1991.

[2] B. Alspach and C.-Q. Zhang, “Hamiltonian cycles in cubic Cayley graphs on dihe-dral groups”, Ars Combinatoria, vol. 28, pp. 101–108, 1989.

[3] T. Araki, “Edge-Pancyclicity of Recursive Circulants”, Information Processing Let-ters, vol. 88, pp. 287–292, 2003.

[5] J. Carle, J.-F. Myoupo, and D. Seme, “All-to-All Broadcasting Algorithms on Hon-eycomb Networks and Applications”, Parallel Processing Letters, vol. 9, pp. 539– 550, 1999.

[6] C.-P. Chang, J.-N. Wang, L.-H. Hsu, “Topological Properties of Twisted Cube”, Information Sciences, vol. 113, pp. 147–167, 1999.