Packing and Covering Complete Bipartite Multidigraphs with 4-Circuits

完全二部重邊有向圖之4迴圈充填與覆蓋

吳文娟(Wen-Chuan Wu) ； 李鴻志(Hung-Chih Lee) ； 林正忠(Jenq-Jong Lin)

《嶺東學報》 24期 (2008/12) Pp. 223-231

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

摘要

設C(下標 k)表長度爲k之有向迴圈。重邊有向圖G中，若一個邊互斥的有向子圖集P={G1, G2,…,G(下標 s)}，其中每個G(下標 i)皆同構於C(下標 k)，則稱P爲G的一個C(下標 k)-充填，若該充填具有最多元素(C(下標 k))，則稱其爲最大C(下標 k)-充填；若一個有向子圖集，R={G1, G2,…, G(下標 t)}，其中每個G(下標 i)皆同構於C(下標 k)，且G的每個邊（重複邊視爲相異邊）至少在R中出現一次，則稱R爲G的一個C(下標 k)-覆蓋，若該覆蓋具有最少元素(C(下標 k))，則稱其爲最小C(下標 k)-覆蓋。本文得到完全二部重邊有向圖之最大C4-充填與最小C4-覆蓋。

關鍵字

充填 ； 覆蓋 ； 完全二部重邊有向圖 ； 有向迴圈 ； 餘圖 ； 超額圖 ； 充填數 ； 覆蓋數

並列摘要

Let C(subscript k) denote a circuit of length k. In a multidigraph G, a C(subscript k)-packing is a set P={G1, G2,…, G(subscript s)} of arc-disjoint subdigraphs of G such that each G(subscript i) is isomorphic to C(subscript k), and a C(subscript k)-packing is maximum if it has the maximum number of members among all packings; a C(subscript k)-covering is a set R={G1, G2,…, G(subscript t)} of subdigraphs of G such that each G(subscript i) is isomorphic to C(subscript k) and every arc of G appears in at least one member of R, and a C(subscript k) covering is minimum if it has the minimum number of members among all coverings. In this paper the problem for finding a maximum C4-packing and a minimum C4-covering of the complete bipartite multidigraph is solved.

並列關鍵字

packing ； covering ； complete bipartite multidigraph ； circuit ； leave ； excess ； packing number ； covering number

參考文獻

C. J. Colbourn,A. Rosa(1987).Quadratic excesses of coverings by triples.Ars Combin.24,23-30.

D. Sotteau(1981).Decomposition of Km,n (K*m,n) into Cycles (Circuits) of Length 2k.J. Comb. Theory.30,75-81.

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

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

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