Packing and covering the balanced complete bipartite multigraph with cycles and stars
Hung-Chih Lee
Abstract
Let Ck denote a cycle of length k
and let Sk denote a star with k
edges. For multigraphs F, G and
H, an (F,G)-decomposition of H
is an edge decomposition of H into copies of
F and G using at least one of each. For
L⊆H and R⊆rH, an
(F,G)-packing (resp. (F,G)-covering) of
H with leave L (resp. padding
R) is an (F,G)-decomposition of
H-E(L) (resp. H+E(R)). An (F,G)-packing
(resp. (F,G)-covering) of H with the largest
(resp. smallest) cardinality is a maximum (F,G)-packing
(resp. minimum (F,G)-covering), and its cardinality is
referred to as the (F,G)-packing number (resp.
(F,G)-covering number) of H. In this paper,
we determine the packing number and the covering number of
λKn,n with Ck's
and Sk's for any λ,
n and k, and give the complete solution of
the maximum packing and the minimum covering of
λKn,n with 4-cycles and
4-stars for any λ and n
with all possible leaves and paddings.
Full Text: PDF PostScript