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.
Similar Articles
- M. Haviar, S. Kurtulík, A new class of graceful graphs: \(k\)-enriched fan graphs and their characterisations , CUBO, A Mathematical Journal: Vol. 23 No. 2 (2021)
- P. Jeyanthi, K. Jeya Daisy, Andrea SemaniÄová-feňovÄíková, \(Z_k\)-magic labeling of path union of graphs , CUBO, A Mathematical Journal: Vol. 21 No. 2 (2019)
- Miroslav Haviar, Katarina Kotuľová, Characterizations of kites as graceful graphs , CUBO, A Mathematical Journal: Vol. 26 No. 3 (2024)
- P. Jeyanthi, A. Maheswari, Odd Vertex Equitable Even Labeling of Cycle Related Graphs , CUBO, A Mathematical Journal: Vol. 20 No. 2 (2018)
- Fernando Levstein, Carolina Maldonado, Generalized quadrangles and subconstituent algebra , CUBO, A Mathematical Journal: Vol. 12 No. 2 (2010): CUBO, A Mathematical Journal
- Sushanta Kumar Mohanta, Common Fixed Point Results in C∗-Algebra Valued b-Metric Spaces Via Digraphs , CUBO, A Mathematical Journal: Vol. 20 No. 1 (2018)
- Eduardo Montenegro, Hamiltonety and automorphisms group of graph preserved by substitution , CUBO, A Mathematical Journal: No. 11 (1995): CUBO, Revista de Matemática
- M. Mohammed Abdul Khayyoom, Characterization of Upper Detour Monophonic Domination Number , CUBO, A Mathematical Journal: Vol. 22 No. 3 (2020)
- Jairo Bochi, Godofredo Iommi, Mario Ponce, Perfect matchings in inhomogeneous random bipartite graphs in random environment , CUBO, A Mathematical Journal: Vol. 24 No. 2 (2022)
- B. Khosravi, M. Khatami, Z. Akhlaghi, Some new characterizations for PGL(2, q) , CUBO, A Mathematical Journal: Vol. 13 No. 2 (2011): CUBO, A Mathematical Journal
You may also start an advanced similarity search for this article.
Downloads
