Packing and Covering Multicrowns with 4-cycles

多重邊皇冠圖之4迴圈充填與覆蓋

李鴻志(Hung-Chih Lee) ； 姚美玉(Mei-Yu Yao)

《嶺東學報》 32期 (2012/12) Pp. 1-17

https://doi.org/10.29850/LTJ.201212.0001

摘要

多重邊皇冠圖λCn,n-1是點集為{a0, a1, ..., an-1, b0, b1,...,bn-1}，而邊集為{aibj (λ重邊) : i = 0,1,...,n-1, j≡i +1, i+2,...,i+n-1 (mod n)}之重邊二部圖。k迴圈是長度為k之迴圈。本文探討多重邊皇冠圖之4迴圈充填與覆蓋問題，且得到所有最大充填與最小覆蓋。

關鍵字

多重邊皇冠圖 ； 迴圈 ； 充填 ； 覆蓋 ； 餘圖 ； 填補圖

並列摘要

A k-cycle is a cycle of length k. The multicrown λCn,n-1 is the multigraph with vertex set {a0, a1, ..., an-1, b0, b1, ..., bn-1} and edge set {aibj with multiplicity λ: i = 0,1,...,n-1, j≡i + 1,i + 2,...,n -1 (mod n)}. In this paper, we completely solve the problem of finding maximum packings and minimum coverings of multicrowns with 4-cycles.

並列關鍵字

multicrown ； cycle ； packing ； covering ； leave ； padding

參考文獻

Billington, E. J.,Fu, H.-L.,Rodger, C. A.(2001).Packing complete multipartite graphs with 4-cycles.Journal of Combinatorial Designs.9,107-127.

Billington, E. J.,Fu, H.-L.,Rodger, C. A.(2005).Packing λ-fold complete multipartite graphs with 4-cycles.Graphs and Combinatorics.21,169-185.

Billington, E. J.,Lindner, C. C.(1996).Maximum packings of uniform group divisible triple systems.Journal of Combinatorial Designs.4,397-404.

Bondy, J. A.,Murty, U. S. R.(1976).Graph Theory with Applications.London:Macmillan Press.

Brown, L.,Coker, G.,Gardner, R.,Kennedy, J.(2005).Packing the complete bipartite graph with hexagons.Congressus Numerantium.174,97-106.