On graphs that have a unique least common multiple
-
Reji T.
rejiaran@gmail.com
-
Jinitha Varughese
jinith@gmail.com
-
Ruby R.
rubymathpkd@gmail.com
Downloads
DOI:
https://doi.org/10.4067/S0719-06462022000100053Abstract
A graph \(G\) without isolated vertices is a least common multiple of two graphs \(H_1\) and \(H_2\) if \(G\) is a smallest graph, in terms of number of edges, such that there exists a decomposition of \(G\) into edge disjoint copies of \(H_1\) and there exists a decomposition of \(G\) into edge disjoint copies of \(H_2\). The concept was introduced by G. Chartrand et al. and they proved that every two nonempty graphs have a least common multiple. Least common multiple of two graphs need not be unique. In fact two graphs can have an arbitrary large number of least common multiples. In this paper graphs that have a unique least common multiple with \( P_3 \cup K_2 \) are characterized.
Keywords
P. Adams, D. Bryant and B. Maenhaut, “Common multiples of complete graphs and a 4-cycle”, Discrete Math., vol. 275, no. 1–3, pp. 289–297, 2004.
P. Adams, D. Bryant, S. I. El-Zanati, C. Vanden Eynden and B. Maenhaut, “Least common multiples of cubes”, Bull. Inst. Combin. Appl., vol. 38, pp. 45–49, 2003.
N. Alon, “A note on the decomposition of graphs into isomorphic matchings”, Acta Math. Hungar., vol. 42, no. 3–4, pp. 221–223, 1983.
D. Bryant and B. Maenhaut, “Common multiples of complete graphs”, Proc. London Math. Soc. (3), vol. 86, no. 2, pp. 302–326, 2003.
G. Chartrand, L. Holley, G. Kubicki and M. Schultz, “Greatest common divisors and least common multiples of graphs”, Period. Math. Hungar., 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 Combin., vol. 46, pp. 177–190, 1997.
G. Chartrand, C. M. Mynhardt and F. Saba, “On least common multiples of digraphs”, Utilitas Math., vol. 49, pp. 45–63, 1996.
Z.-C. Chen and T.-W. Shyu, “Common multiples of paths and stars”, Ars Combin., vol. 146, pp. 115–122, 2019.
O. Favaron, Z. Lonc and M. TruszczyÅ„ski, “Decompositions of graphs into graphs with three edges”, Ars Combin., vol. 20, pp. 125–146, 1985.
O. Favaron and C. M. Mynhardt, “On the sizes of least common multiples of several pairs of graphs”, Ars Combin., vol. 43, pp. 181–190, 1996.
C. M. Mynhardt and F. Saba, “On the sizes of least common multiples of paths versus complete graphs”, Utilitas Math., vol. 46, pp. 117–127, 1994.
T. Reji, “On graphs that have a unique least common multiple with matchings”, Far East J. Appl. Math., vol. 18, no. 3, pp. 281–288, 2005.
C. Sunil Kumar, “Least common multiple of a cycle and a star”, Electron. Notes Discrete Math., vol. 15, pp. 204–206, 2003.
P. Wang, “On the sizes of least common multiples of stars versus cycles‘”, Util. Math., vol. 53, pp. 231–242, 1998.
Downloads
