Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graph decomposition; path; star graph; product graph
graph decomposition; path; star graph; product graph
Summary:
Let $P_k$ and $S_k$ denote a path and a star, respectively, on $k$ vertices. We give necessary and sufficient conditions for the existence of a complete $\{P_5,S_5\}$-decomposition of Cartesian product of complete graphs.
References:
[1] Abueida A. A., Daven M.: Multidesigns for graph-pairs of order 4 and 5. Graphs Combin. 19 (2003), no. 4, 433–447. DOI 10.1007/s00373-003-0530-3
[2] Abueida A. A., Daven M.: Multidecompositions of the complete graph. Ars Combin. 72 (2004), 17–22.
[3] Abueida A. A., Daven M., Roblee K. J.: Multidesigns of the $\lambda$-fold complete graph for graph-pairs of orders 4 and 5. Australas. J. Combin. 32 (2005), 125–136.
[4] Abueida A. A., O'Neil T.: Multidecomposition of $\lambda K_m$ into small cycles and claws. Bull. Inst. Combin. Appl. 49 (2007), 32–40.
[5] Bondy J. A., Murty U. S. R.: Graph Theory with Applications. American Elsevier Publishing, New York, 1976.
[6] Ezhilarasi A. P., Muthusamy A.: Decomposition of product graphs into paths and stars with three edges. Bull. Inst. Combin. Appl. 87 (2019), 47–74.
[7] Jeevadoss S., Muthusamy A.: Decomposition of product graphs into paths and cycles of length four. Graphs Combin. 32 (2016), 199–223. DOI 10.1007/s00373-015-1564-z
[8] Priyadharsini H. M., Muthusamy A.: $(G_m, H_m)$-multidecomposition of $K_{m,m}(\lambda)$. Bull. Inst. Combin. Appl. 66 (2012), 42–48.
[9] Shyu T.-W.: Decomposition of complete graphs into paths and stars. Discrete Math. 310 (2010), no. 15–16, 2164–2169.
[10] Shyu T.-W.: Decomposition of complete bipartite graphs into paths and stars with same number of edges. Discrete Math. 313 (2013), no. 7, 865–871. DOI 10.1016/j.disc.2012.12.020
Search
Partner of
