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 (2014) 189–202.
https://doi.org/10.46298/DMTCS.2091 - 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.
https://doi.org/10.11650/tjm.19.2015.4456 - 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.
https://doi.org/10.1016/j.disc.2013.06.014 - C. Lin, J.J. Lin and 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.
https://doi.org/10.1137/050626363 - S. Yamamoto, H. Ikeda, S. Shige-eda, K. Ushio and N. Hamada, On claw decomposition of complete graphs and complete bipartie graphs, Hiroshima Math. J. 5 (1975) 33–42.
https://doi.org/10.32917/hmj/1206136782
Close