Common Multiples of Paths and Stars with Crowns




Graph Decomposition, Common Multiples of Graphs, Path, Star, Crown


{\footnotesize A graph $G$ is a common multiple of two graphs $H_1$ and $H_2$ if there exists a decomposition of $G$ into edge-disjoint copies of $H_1$ and also a decomposition of $G$ into edge-disjoint copies of $H_2$. If $ G $ is a common multiple of $H_1$ and $H_2$, and $ G $ has $ q $ edges, then we call $ G $ a $ (q, H_1, H_2) $ graph. Our paper deals with the following question: Given two graphs $ H_1 $ and $ H_2$, for which values of $ q $ does there exist a $ (q, H_1, H_2) $ graph? when $H_1$ is either a path or a star with $3$ or $4$ edges and $H_2$ is a crown.


P. Adams, D. E. Bryant, S. I. El-Zanati, C. Vanden Eynden, and B.

Maenhaut, “Least common multiples of cubes”, Bulletin of the Institute of Combinatorics and its Applications, Vol. 38, pp. 45-49, 2003.

P. Adams, D. Bryant, and B. Maenhaut,“Common multiples of complete graphs and a 4-cycle.” Discrete mathematics, Vol. 275, No. 1-3, pp. 289-297, 2004.

G. Chartrand, L. Holley, G. Kubicki, and M. Schultz,“Greatest common divisors and least common multiples of graphs.” Periodica Mathematica Hungarica, Vol. 27, No. 2, pp. 95-104, 1993.

G. Chartrand, G. Kubicki, C. M. Mynhardt, and F. Saba, “On graphs

with a unique least common multiple.” Ars Combinatoria, Vol. 46, pp.

-190, 1997.

G. Chartrand, C. M. Mynhardt, and F. Saba,“On least common multiples of digraphs.” Utilitas Mathematica, Vol. 49, 1996.

Z.-C. Chen, T.-W. Shyu, et al.,“Common multiples of paths and stars.”

ARS COMBINATORIA, Vol. 146, pp. 115-122, 2019.

D. Bryant and B. Maenhaut, “Common multiples of complete graphs.”

Proceedings of the London Mathematical Society, Vol. 86, No. 2, pp.

-326, 2003.

O. Favaron and C. M. Mynhardt, “On the sizes of least common multiples of several pairs of graphs.” Ars Combinatoria, Vol. 43, pp. 181-190,

C. Lin, J.-J. Lin, and T.-W. Shyu, “Complete bipartite decompositions

of crowns, with applications to complete directed graphs.” Combinatorics and Computer Science: 8th Franco-Japanese and 4th FrancoChinese Conference Brest, France, July 3-5, 1995 Selected Papers, pp.

-66, Springer, 1996.

C. Lin, J. J. Lin, and T. W. Shyu, “Isomorphic star decompositions of

multicrowns and the power of cycles.” Ars Combinatoria, Vol. 53, pp.

-256, 1999.

C. Mynhardt and F. Saba, “On the sizes of least common multiples

of paths versus complete graphs.” UTILITAS MATHEMATICA, Vol.

, pp. 117-128, 1994.

C. A. Parker, Complete bipartite graph path decompositions, Ph.D.

Dissertation, Auburn University, Auburn, Alabama, 1998.

T. Reji, Saritha Chandran C, “Common multiples of paths and stars

with complete graphs”, Gulf Journal of Mathematics, Vol. 12 (1), pp.

-14, 2022.

T. Reji, Saritha Chandran C, “Common multiples of path, star, and

cycle with Complete bipartite graphs”, South East Asian J. of Mathematics and Mathematical Sciences, Vol. 18, No. 1, pp. 351-362, 2022.

T. W. Shyu and C. Lin, “Isomorphic path decompositions of crowns.”

Ars Combinatoria, Vol. 67, pp. 97-103, 2003.

P. Wang, “On the sizes of least common multiples of stars versus cycles.” Utilitas Mathematica, Vol. 53, 1998.



How to Cite

S. . Chandran C. and R. . T., “Common Multiples of Paths and Stars with Crowns ”, Proyecciones (Antofagasta, On line), vol. 43, no. 2, pp. 331-344, Apr. 2024.




Most read articles by the same author(s)