Minimum Leaves of Complete Multidigraphs by Packing Directed 4-cycles

有向4迴圈充填完全重邊有向圖之最小餘圖

姚美玉(Mei-Yu Yao) ； 林正忠(Jenq-Jong Lin) ； 李鴻志(Hung-Chih Lee)

《嶺東學報》 25期 (2009/06) Pp. 1-10

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

摘要

設C4表有向4迴圈。完全重邊有向圖G中，C4-充填P是一個邊互斥的C4集，充填P的餘圖L是不在P中的邊子集，即L=G-P；若餘圖L的邊數最少則稱爲最小餘圖。本文得到完全重邊有向圖之C4-充填的所有最小餘圖。

關鍵字

餘圖 ； 充填 ； 完全重邊有向圖 ； 有向迴圈

並列摘要

Let C4 denote a directed 4-cycle. A C4-packing P of a multidigraph G is a set of arc-disjoint C4's in G. A leave L of a C4-packing P of G is the set of arcs of G that occur in no C4 of P, that is, L=G-P. A leave L for C4-packing of G is minimum if |L| is as small as possible. In this paper the minimum leaves for packing complete multidigraphs with directed 4-cycles are completely determined.

並列關鍵字

leave ； packing ； complete multidigraph ； directed cycle

參考文獻

Alspach, B.,Gavlas, H.(2001).Cycle decompositions of Kn and Kn- I.J. Comb. Theory, Ser. B.81,77-99.

Alspach, B.,Gavlas, H.,Šajna, M.,Verrall, H.(2003).Cycle decompositions IV: complete directed graphs and fixed length directed cycles.J. Comb. Theory Ser. A.103,165-208.

Bosák, J.(1990).Decompositions of Graphs.Dordrecht, Netherlands:Kluwer.

Fort, M. K., Jr.,Hedlund, G. A.(1958).Minimal coverings of pairs by triples.Pac. J. Math.8,709-719.

Hoffman, D. G.,Lindner, C. C.,Rodger, C. A.(1989).On the construction of odd cycle system.J. Graph Theory.13,417-426.