Hung-Chih Lee - Packing and covering the balanced complete bipartite multigraph with cycles and stars

dmtcs:2091 - Discrete Mathematics & Theoretical Computer Science, September 25, 2014, Vol. 16 no. 3 - https://doi.org/10.46298/dmtcs.2091
Packing and covering the balanced complete bipartite multigraph with cycles and starsArticle

Authors: Hung-Chih Lee 1

  • 1 Department of Combinatorial Models and Algorithms [Minsk]

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.


Volume: Vol. 16 no. 3
Section: Graph Theory
Published on: September 25, 2014
Submitted on: November 24, 2013
Keywords: complete bipartite multigraph,cycle,star,packing,covering,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 316 times.
This article's PDF has been downloaded 461 times.