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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.189--202
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01188905
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 31 août 2015 - 17:03:24
Dernière modification le : jeudi 7 septembre 2017 - 01:03:47
Document(s) archivé(s) le : mardi 1 décembre 2015 - 10:42:50

Fichier

dmtcs-16-3-10.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

57

Téléchargements de fichiers

293