Skip to Main content Skip to Navigation
Journal articles

Packing and covering the balanced complete bipartite multigraph with cycles and stars

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01188905
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 31, 2015 - 5:03:24 PM
Last modification on : Thursday, September 7, 2017 - 1:03:47 AM
Long-term archiving on: : Tuesday, December 1, 2015 - 10:42:50 AM

File

dmtcs-16-3-10.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01188905, version 1

Collections

Citation

Hung-Chih Lee. Packing and covering the balanced complete bipartite multigraph with cycles and stars. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.189--202. ⟨hal-01188905⟩

Share

Metrics

Record views

97

Files downloads

1021