多重完全圖之混合分解

Abstract

所謂的k點的圖對(G,H)是指不同構的兩個k點圖，它們滿足(1) G與H中都不具有孤立點，及(2) G與H的圖聯集恰為k點的完全圖。如果我們可以把n點的完全圖用G與H的組合來表示，每一個至少出現一次，我們稱這樣的分割為雙重圖設計。更進一步，如果對於所有的s與t，只要滿足λ(n)(n-1)/2=s|E(G)|+t|E(H)|，就可以用s個圖G與t個圖H來組合成λKn，則我們稱這樣的一個分割為λ倍的混合設計，或多重混合設計。 在這篇論文中，我們針對一個5點的圖對（各有5邊），分別建構出多重混合設計，多重混合裝填及多重混合覆蓋；後兩者是在λ(n)(n-1)/2不為5的倍數時分別討論最大裝填及最小覆蓋。