Article in volume
Authors:
Title:
Minimum coverings of crowns with cycles and stars
PDFSource:
Discussiones Mathematicae Graph Theory 42(1) (2022) 81-88
Received: 2018-10-22 , Revised: 2019-07-07 , Accepted: 2019-07-07 , Available online: 2019-10-01 , https://doi.org/10.7151/dmgt.2241
Abstract:
Let $F$, $G$ and $H$ be graphs. A $(G,H)$-decomposition of $F$ is
a partition of the edge set of $F$ into copies of $G$ and copies of $H$ with
at least one copy of $G$ and at least one copy of $H$. For $R\subseteq F$,
a $(G,H)$-covering of $F$ with padding $R$ is a
$(G,H)$-decomposition of $F+E(R)$. A $(G,H)$-covering of $F$ with the smallest
cardinality is a minimum $(G,H)$-covering. This paper gives the solution
of finding the minimum $(C_k,S_k)$-covering of the crown $C_{n,n-1}$.
Keywords:
cycle, star, covering, decomposition, crown
References:
- H. C. Lee, Multidecompositions of complete bipartite graphs into cycles and stars, Ars Combin. 108 (2013) 355–364.
- H. C. Lee, Packing and covering the balanced complete bipartite multigraph with cycles and stars, Discrete Math. Theor. Comput. Sci. 16:3 (2014) 189–202.
- H. C. Lee and Z. C. Chen, Maximum packings and minimum coverings of multigraphs with paths and stars, Taiwanese J. Math. 19 (2015) 1341–1357.
- H. C. Lee and J. J. Lin, Decomposition of the complete bipartite graph with a $1$-factor removed into cycles and stars, Discrete Math. 313 (2013) 2354–2358.
- C. Lin, J. J. Lin, T. W. Shyu, Isomorphic star decomposition of multicrowns and the power of cycles, Ars Combin. 53 (1999) 249–256.
- J. Ma, L. Pu and H. Shen, Cycle decompositions of $K_{n,n}-I$, SIAM J. Discrete Math. 20 (2006) 603–609.
- S. Yamamoto, H. Ikeda, S. Shige-ede, K. Ushio and N. Hamada, On claw decomposition of complete graphs and complete bipartie graphs, Hiroshima Math. J. 5 (1975) 33–42.
Close