Decompositions of complete multigraphs into stars of varying sizes

DOI10.1016/J.JCTB.2020.05.001MaRDI QIDQ2200917zbMATH OpenOpenAlexFDO

Authors Rosalind A. Cameron, Daniel Horsley

Publication date 24 September 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.10738

complete multigraph edge decomposition NP-completeness star tournament

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size

m

exists whenever some obvious necessary conditions hold. In 1992 Lonc gave necessary and sufficient conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes

m_{1}, l d o t s, m_{t}

. We show that the general problem of when a complete multigraph admits a decomposition into stars of sizes

m_{1}, l d o t s, m_{t}

is

m a t h s f N P

-complete, but that it becomes tractable if we place a strong enough upper bound on

m a x (m_{1}, l d o t s, m_{t})

. We determine the upper bound at which this transition occurs. Along the way we also give a characterisation of when an arbitrary multigraph can be decomposed into stars of sizes

m_{1}, l d o t s, m_{t}

with specified centres, and a generalisation of Landau's theorem on tournaments.

Review text

An \(m\)-star is a complete bipartite graph \(K_{1,m}\); for an integer \(\lambda\ge1\), \(\lambda K_n\) denotes the multigraph obtained from the underlying graph \(K_n\) by assigning to each of its edges the multiplicity \(\lambda\). This paper generalizes to multigraphs a numerical characterization [\textit{Z. Lonc}, J. Comb. Theory, Ser. A 61, No. 2, 263--278 (1992; Zbl 0763.04004); \textit{C. Lin} and \textit{T.-W. Shyu}, J. Graph Theory 23, No. 4, 361--364 (1996; Zbl 0880.05069)] for the existence of a decomposition of \(K_n\) into stars of specified sizes. The authors formulate a primary question, \((\lambda,\alpha)\)-STAR DECOMP, as a family of decision problems, one for each integer \(\lambda\ge1\) and real \(\alpha\in{\mathbb R}\) such that \(0\le\alpha\le1\): if \(n\) and \(m_1,\dots,m_t\) are positive integers such that \(\max\left\{m_1,\dots,m_t\right\}\le\alpha(n-1)\) and \(m_1+\dots+m_t=\lambda\cdot {\binom n 2}\), does the multigraph \(\lambda K_n\) admit a decomposition into disjoint stars of sizes \(m_1,\dots,m_t\)? The main theorem is: Theorem 1: Let \(\lambda\ge2\). Then \((\lambda,\alpha)\)-STAR DECOMP is NP-complete if \(\alpha>\alpha^\prime\), where \(\alpha^\prime=\frac\lambda{\lambda+1}\) if \(\lambda\) is odd, and \(\alpha^\prime=1-\frac2\lambda\cdot\left(3-2\sqrt{2}\right)\) if \(\lambda\) is even. Furthermore, if \(\alpha\le\alpha^\prime\), then every instance of \((\lambda,\alpha)\)-STAR DECOMP is feasible and the required decompositions can be constructed in polynomial time. This theorem is proved as a consequence of a second theorem, as another application of which the authors are able to generalize to orientations of a multigraph a theorem of Landau which characterises when there exists a 1-fold tournament with specified degrees [\textit{H. G. Landau}, ``On dominance relations and the structure of animal societies. III: The condition for a score structure, Bull. Math. Biophys. 15, 143--148 (1953; \url{doi:10.1007/BF02476378})].

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Decompositions of complete multigraphs into stars of varying sizes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200917)