Packing and covering the balanced complete bipartite multigraph with cycles and stars - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Discrete Mathematics and Theoretical Computer Science Year : 2014

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.
Fichier principal
Vignette du fichier
dmtcs-16-3-10.pdf (301.19 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-01188905 , version 1 (31-08-2015)

Identifiers

Cite

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

Collections

TDS-MACS
44 View
935 Download

Altmetric

Share

Gmail Facebook X LinkedIn More