×

Optimal packings and coverings of \(\lambda\)DK\(_v\). (English) Zbl 0989.05094

Summary: Let \(\lambda\text{DK}_v\) denote the complete directed multigraph with \(v\) vertices, where any two distinct vertices \(x\) and \(y\) are joined by \(\lambda\) arcs \((x, y)\) and \(\lambda\) arcs \((y, x)\). By a \(k\)-circuit we mean a directed cycle of length \(k\). In this paper, we consider the problem of constructing maximal packings and minimal coverings of \(\lambda\text{DK}_v\) with \(k\)-circuits. Using the leave-arcs graph of packing and the repeat-arcs graph of covering, we give a unified method for finding packings and coverings. Also, we completely solve the existence of optimal packings and coverings for \(5\leq k\leq 14\) and any \(\lambda\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B40 Combinatorial aspects of packing and covering
PDFBibTeX XMLCite