圈分割的極圖

Abstract

如果一個圖G的邊集合可以分成一些子集合的聯集，而每一個子集合都導出一個k圈，圖G就稱為有k圈分割。很明顯地，如果圖G有k圈分割，圖G一定是一個偶圖，而且k會整除圖G的邊數。我們稱一個滿足上面兩個條件的圖為k充分圖。不難發現，一個k充分圖可能沒有k圈分割。在論文中的第一部份，將探討一個有n個點，是r正則且k充分，但是卻不存在k圈分割的圖。利用直接建構法說明，r是如何根據k和n的不同，得到不同的下界。第二部份，探討沒有k圈分割的極圖，根據圈大小的不同，也得到不同邊數的下界。