CUBO, A Mathematical Journal Vol. 24, no. 01, pp. 53–62, April 2022 DOI: 10.4067/S0719-06462022000100053 On graphs that have a unique least common multiple Reji T. 1 Jinitha Varughese 2 Ruby R. 1 1Department of Mathematics, Government College Chittur Palakkad, India. rejiaran@gmail.com rubymathpkd@gmail.com 2Department of Mathematics, B. K. College Amalagiri, Kottayam, India. jinith@gmail.com ABSTRACT A graph G without isolated vertices is a least common multi- ple of two graphs H1 and H2 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 H1 and there exists a decom- position of G into edge disjoint copies of H2. 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 P3 ∪ K2 are characterized. RESUMEN Un grafo G sin vértices aislados es un mı́nimo común múltiplo de dos grafos H1 y H2 si G es uno de los grafos más pequeños, en términos del número de ejes, tal que existe una descomposición de G en copias de H1 disjuntas por ejes y existe una descomposición de G en copias de H2 disjun- tas por ejes. El concepto fue introducido por G. Chartrand et al. donde ellos demostraron que cualquera dos grafos no vaciós tienen un mı́nimo común múltiplo. El mı́nimo común múltiplo de dos grafos no es necesariamente único. De hecho, dos grafos pueden tener un número arbitrariamente grande de mı́nimos comunes múltiplos. En este art́ıculo caracteri- zamos los grafos que tienen un único mı́nimo común múltiplo con P3 ∪ K2. Keywords and Phrases: Graph decomposition, common multiple of graphs. 2020 AMS Mathematics Subject Classification: 05C38, 05C51, 05C70. Accepted: 03 November, 2021 Received: 23 March, 2021 c©2022 Reji T. et al. This open access article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. http://cubo.ufro.cl/ http://dx.doi.org/10.4067/S0719-06462022000100053 https://orcid.org/0000-0003-2712-3775 https://orcid.org/0000-0003-4419-6626 https://orcid.org/0000-0001-5473-6492 mailto:rejiaran@gmail.com mailto:rubymathpkd@gmail.com mailto:jinith@gmail.com 54 Reji T., Jinitha Varughese & Ruby R. CUBO 24, 1 (2022) 1 Introduction All graphs considered in this paper are assumed to be simple and to have no isolated vertices. The number of edges of a graph G denoted by e(G), is called the size of G. δ(G) and ∆(G) respectively denote the minimum and maximum of the degrees of all vertices in G. χ′(G) denotes the edge chromatic number of G, the minimum number of colors needed to color the edges of G, so that no two adjacent edges in G have the same color. An odd component of a graph is a maximal connected subgraph of the graph with odd number of edges. Two graphs G and H are said to be isomorphic, denoted as G ∼= H if there exists a bijection between the vertex sets of G and H, f : V (G) → V (H) such that two vertices u and v of G are adjacent in G if and only if f(u) and f(v) are adjacent in H. For graphs G1 and G2, their union G1 ∪ G2 is the graph with vertex set V (G1 ∪ G2) = V (G1) ∪ V (G2) and edge set consisting of all the edges in G1 together with all the edges in G2. If k is a positive integer, then kG is the union of k disjoint copies of G. G1 v1 v2 G2 v3 v4 v5 G3 v6 v7 v8 v1 v2 v3 v4 v5 Figure 1: G1 ∪ G2 Let G = G2. Then G ∼= G3 and 2G is shown in Figure 2. v3 v4 v5 v6 v7 v8 Figure 2: 2G A vertex u of a graph G is said to cover an edge e of G or e is covered by u, if e is incident with u. Let u, w be two vertices of a graph G and take two copies of G : G1, G2. The graph H obtained by identifying the vertex u in G1 with the vertex w in G has vertex set V (H) = V (G1)∪V (G2)−{w} and edge set E(H) = E(G1) ∪ E(G2), where the edges in G2 incident with w are now incident with u. A graph H is said to divide a graph G if there exists a set of subgraphs of G, each isomorphic to H, whose edge sets partition the edge set of G. Such a set of subgraphs is called an H-decomposition CUBO 24, 1 (2022) On graphs that have a unique least common multiple 55 of G. If G has an H-decomposition, we say that G is H-decomposable and write H|G. A graph is called a common multiple of two graphs H1 and H2 if both H1|G and H2|G. A graph G is a least common multiple of H1 and H2 if G is a common multiple of H1 and H2 and no other common multiple has a smaller positive number of edges. Several authors have investigated the problem of finding least common multiples of pairs of graphs H1 and H2; that is graphs of minimum size which are both H1 and H2 decomposable. The problem was introduced by Chartrand et al. in [5] and they showed that every two nonempty graphs have a least common multiple. The problem of finding the size of least common multiples of graphs has been studied for several pairs of graphs: cycles and stars [5,13,14], paths and complete graphs [11], pairs of cycles [10], pairs of complete graphs [4], complete graphs and a 4-cycle [1], pairs of cubes [2] and paths and stars [8]. Least common multiple of digraphs were considered in [7]. If G is a common multiple of H1 and H2 and G has q edges, then we call G a (q, H1, H2) graph. An obvious necessary condition for the existence of a (q, H1, H2) graph is that e(H1)|q and e(H2)|q. This obvious necessary condition is not always sufficient. Therefore, we may ask: Given two graphs H1 and H2, for which value of q does there exist a (q, H1, H2) graph? Adams, Bryant and Maenhaut [1] gave a complete solution to this problem in the case where H1 is the 4-cycle and H2 is a complete graph; Bryant and Maenhaut [4] gave a complete solution to this problem when H1 is the complete graph K3 and H2 is a complete graph. The problem to find least common multiples of two graphs H1 and H2 is to find all (q, H1, H2) graphs G of minimum size q. We denote the set of all least common multiples of H1 and H2 by LCM(H1, H2). The size of a least common multiple of H1 and H2 is denoted by lcm(H1, H2). Since every two nonempty graphs have a least common multiple, LCM(H1, H2) is nonempty. For many pairs of graphs the number of elements of LCM(H1, H2) is greater than one. For example both P7 and C6 are least common multiples of P4 and P3. In fact Chartrand et al. [6] proved that for every positive integer n there exist two graphs having exactly n least common multiples. In [11] it was shown that every least common multiple of two connected graphs is connected and that every least common multiple of two 2-connected graphs is 2-connected. But this is not the case for disconnected graphs. For example if we take H1 = 2K2, H2 = C5, then G1 = 2C5 and G2 - the graph obtained by identifying two vertices in two copies of C5, are in LCM(H1, H2) of which G1 is disconnected while G2 is connected. As two graphs can have several least common multiples, it is interesting to search for pairs of graphs that have a unique least common multiple. Pairs of graphs having a unique least common multiple were investigated by G. Chartrand et al. in [6] and they proved the following results. Theorem 1.1. A graph G of order p without isolated vertices and the graph P3 have a unique least common multiple if and only if every component of G has even size or G ∼= Kp, where p ≡ 2 or 3 (mod 4). Theorem 1.2. A nonempty graph G without isolated vertices and the graph 2K2 have a unique 56 Reji T., Jinitha Varughese & Ruby R. CUBO 24, 1 (2022) least common multiple if and only if G ∼= K2, G ∼= K3 or 2K2|G. Theorem 1.3. Let r and s be integers with 2 ≤ r ≤ s. Then the stars K1,r and K1,s have a unique least common multiple if and only if gcd(r, s) 6= 1. A result proved by N. Alon [3] on tK2-decomposition of a graph is used to find those graphs that have a unique least common multiple with tK2. Theorem 1.4. For every graph G and every t > 1, tK2|G if and only if t|e(G) and χ ′(G) ≤ e(G) t . We will also make use of a result proved by O. Favaron, Z. Lonc and M. Truszczynski [9] to characterize those graphs that have a unique least common multiple with P3 ∪ K2. Theorem 1.5. If G is none of the six graphs G1 to G6 listed below, then G is P3∪K2 decomposable if and only if (1) e(G) ≡ 0 (mod 3), (2) ∆(G) ≤ 2 3 e(G), (3) c(G) ≤ 1 3 e(G), where c(G) denote the number of odd components of G, (4) the edges of G cannot be covered by two adjacent vertices; where, G1 G2 G3 G4 G5 G6 2 Main results In this section we are characterizing those graphs that have a unique least common multiple with tK2 and P3 ∪ K2. CUBO 24, 1 (2022) On graphs that have a unique least common multiple 57 2.1 On graphs that have a unique least common multiple with tK2 Theorem 2.1. A nonempty graph G without isolated vertices and the graph tK2 have a unique least common multiple if and only if tK2|G or δ(G) > lcm(tK2, G) 2t . Proof. Consider the graph tG. Clearly tG is both G and tK2 decomposable. Let q = e(G). Since e(tG) = tq, we have lcm(tK2, G) ≤ tq. But lcm(tK2, G) is a multiple of q. So lcm(tK2, G) = ql, where l ≤ t. This implies lcm(tK2,G) t = ql t . Let H be a least common multiple of G and tK2. Case 1. l > 1. Since H is tK2-decomposable, by Theorem 1.4, χ ′(H) ≤ ql t . Since G|H, χ′(G) ≤ χ′(H) ≤ ql t . Thus ∆(G) ≤ ql t . Subcase (i): δ(G) ≤ ql 2t . Consider the graph G ◦ G, which is obtained by identifying two vertices of least degree in G. In this subcase ∆(G ◦ G) ≤ ql t , since ∆(G) ≤ ql t . χ′(G) ≤ ql t implies χ′(G ◦ G) ≤ ql t . Color G1, a copy of G in G ◦ G, with k ≤ ql t colors. This is possible, since χ′(G) ≤ ql t . Let v be the identified vertex in G◦G. Since δ(G) ≤ ql 2t , the edges adjacent to v in G1 are colored using at most ql 2t colors. Color G2, the copy of G in G◦G other than G1, with the same k colors as follows. Color the edges adjacent to v in G2 using colors different from those which were used to color the edges adjacent to v in G1. The remaining colors used in the coloring of G1 can be used to color other edges of G2. Thus χ ′(G ◦ G) = k ≤ ql t . Let H1 = lG, the union of l disjoint copies of G and H2 = G◦ G∪(l − 2)G. Clearly H1 and H2 are divisible by G. Since χ′(H1) = χ ′(G) ≤ ql t , H1 is tK2-decomposable. χ ′(H2) = χ ′(G ◦ G) ≤ ql t , H2 is tK2-decomposable by Theorem 1.4. Thus H1, H2 ∈ LCM(tK2, G). e(H1) = e(H2) = ql, where q = e(G). Since lcm(tK2, G) = ql, H1 and H2 are two non-isomorphic least common multiples of tK2 and G. Subcase (ii): δ(G) > ql 2t . In this case l > 1 and lcm(tK2, G) = ql, where q = e(G). Thus H ∈ LCM(tK2, G), should be decomposed into at least two copies of G. If H is different from lG, then ∆(H) > ql t which implies χ′(H) > ql t and hence by Theorem 1.4, H is not tK2-decomposable. Thus lG is the unique least common multiple of tK2 and G. Case 2. l = 1. In this case lcm(tK2, G) = q. Thus tK2|G and G is the unique least common multiple. Remark 2.2. The result in the above theorem, Theorem 2.1, appeared in [12]. We are giving the proof of this result here since the result is needed for proving Theorem 2.3. The result was proved 58 Reji T., Jinitha Varughese & Ruby R. CUBO 24, 1 (2022) by the first author of this manuscript. 2.2 On graphs that have a unique least common multiple with P3 ∪ K2 Theorem 2.3. A nonempty graph G without isolated vertices and the graph P3 ∪K2 have a unique least common multiple if and only if G = K2 or P3 ∪ K2 | G. Proof. Let q = e(G). Case 1. G is a connected graph. If G = K2, then G | P3 ∪K2. Thus LCM(P3 ∪K2, K2) = {P3 ∪K2} and hence their least common multiple is unique. So we are going to analyse the case where G 6= K2. Consider the graph 3G, a union of three disjoint copies of G. Then (1) e(3G) ≡ 0 (mod 3). (2) ∆(3G) = ∆(G) ≤ q = 1 3 (3q) ≤ 2 3 (3q) = 2 3 e(3G). (3) c(3G) ≤ 3 ≤ 1 3 (3q) = 1 3 e(3G), if e(G) ≥ 3. If e(G) = 2, then c(3G) = 0 ≤ 1 3 e(3G). (4) The edges of 3G cannot be covered by two adjacent vertices, since the graph is disconnected. Thus by Theorem 1.5, 3G is P3∪K2-decomposable. Clearly 3G is G-decomposable. Hence lcm(P3∪ K2, G) ≤ 3q. Subcase (i): lcm(P3 ∪ K2, G) = 3q. Consider the graph H = G◦G∪G, where G◦G is the graph obtained by identifying a least degree vertex in two copies of G. Then (1) e(H) ≡ 0 (mod 3). (2) ∆(H) ≤ 2q = 2 3 (3q) = 2 3 e(H). (3) c(H) ≤ 1 ≤ 1 3 (3q) = 1 3 e(H). (4) Since H is disconnected, edges of H cannot be covered by two adjacent vertices. Thus by Theorem 1.5, H is P3 ∪ K2- decomposable. Clearly H is G- decomposable. Hence in this case both H and 3G are elements of LCM(P3 ∪ K2, G) and hence their least common multiple is not unique. Subcase (ii): lcm(P3 ∪ K2, G) = 2q. In this case there exists a graph H such that e(H) = 2q and H ∈ LCM(P3 ∪ K2, G). Consider the graph 2G. CUBO 24, 1 (2022) On graphs that have a unique least common multiple 59 (1) Since H ∈ LCM(P3 ∪ K2, G) we get 3 | e(H) = 2q = e(2G) and hence e(2G) ≡ 0 (mod 3). (2) Since H is G-decomposable and ∆(G) = ∆(2G), ∆(2G) ≤ ∆(H). H is P3∪K2-decomposable and so by Theorem 1.5, ∆(H) ≤ 2 3 e(H) = 2 3 e(2G). Thus ∆(2G) ≤ 2 3 e(2G). (3) In this case q ≥ 3 ( if q = 1, then G = K2 and if q = 2, then e(2G) = 4 6≡ 0 (mod 3) ) . So c(2G) ≤ 2 ≤ 1 3 2q = 1 3 e(2G). (4) Since 2G is disconnected, the edges of 2G cannot be covered by two adjacent vertices. By applying Theorem 1.5, 2G is P3 ∪ K2-decomposable. 2G is clearly G-decomposable. Thus 2G ∈ LCM(P3 ∪ K2, G). We can also prove that G ◦ G ∈ LCM(P3 ∪ K2, G). (1) e(G ◦ G) = e(2G) ≡ 0 (mod 3). (2) In order to prove that ∆(G ◦ G) ≤ 2 3 e(G ◦ G) it is enough to prove that ∆(G) and 2δ(G) are less than or equal to 2 3 e(G ◦ G), since G ◦ G is obtained by identifying a vertex of least degree in two copies of G. Since H ∈ LCM(P3 ∪ K2, G), ∆(G) ≤ ∆(H) ≤ 2 3 e(H) = 2 3 e(G ◦ G). 2δ(G) ≤ 2 3 e(G ◦ G) ⇐⇒ δ(G) ≤ 2q 3 . Suppose δ(G) > 2q 3 . Then 2q = ∑ v∈V (G) d(v) ≥ ∑ v∈V (G) δ(G) = nδ(G) > n 2q 3 , where n = |V (G)|. This implies n < 3. G is a connected graph without isolated vertices and G 6= K2. Thus n ≥ 3 and so δ(G) ≤ 2q 3 . (3) c(G ◦ G) = 0 < 1 3 e(G ◦ G). (4) The edges of G ◦ G cannot be covered by two adjacent vertices. Suppose the edges of G ◦ G can be covered by two adjacent vertices, then the identified vertex is one such vertex, since in G ◦ G, no two vertices are adjacent except the identified vertex. This implies using the identified vertex and one other vertex it is possible to cover all the edges of G ◦ G. This is possible only if G is a star with the identified vertex as the center of the star. This is a contradiction, since to construct G ◦ G a vertex of least degree in G is identified. Applying Theorem 1.5, G ◦ G is P3 ∪ K2- decomposable and it is clearly G-decomposable. So G ◦ G ∈ LCM(P3 ∪ K2, G). We have proved that 2G and G ◦ G ∈ LCM(P3 ∪ K2, G) and hence their least common multiple is not unique. Subcase (iii): lcm(P3 ∪ K2, G) = q. In this subcase G is the unique least common multiple, since q = e(G). Case 2. G is disconnected. 60 Reji T., Jinitha Varughese & Ruby R. CUBO 24, 1 (2022) As in the first case, assume that G 6= tK2. Then at least one component of G has more than one edge. We construct a graph of size 3q, which is a (3q, G, P3 ∪ K2)-graph, where q = e(G). The construction is as follows. Take a least degree vertex from each component of G. Let H be the connected graph obtained by identifying all these vertices together. Take a least degree vertex in H. Denote by H ◦ H ◦ H, the graph obtained by identifying this least degree vertex in three copies of H. (1) e(H ◦ H ◦ H) = e(3H) = 3e(G) ≡ 0 (mod 3). (2) ∆(H ◦ H ◦ H) ≤ 2∆(H) ≤ 2e(G) = 2 3 e(3G) = 2 3 e(H ◦ H ◦ H). (3) c(H ◦ H ◦ H) ≤ 1 ≤ 1 3 e(H ◦ H ◦ H). (4) As in Subcase (ii) of the previous case, the edges of H ◦ H ◦ H cannot be covered by two adjacent vertices. By Theorem 1.5, H ◦ H ◦ H is P3 ∪ K2-decomposable and obviously it is G-decomposable. Thus lcm(P3 ∪ K2, G) ≤ 3q. Subcase (i): lcm(P3 ∪ K2, G) = 3q. From the above discussion H ◦ H ◦ H is a least common multiple in this subcase. Consider the graph H ◦ H ∪ H. (1) e(H ◦ H ∪ H) = 3e(G) ≡ 0 (mod 3). (2) ∆(H ◦ H ∪ H) ≤ 2∆(H) ≤ 2e(G) = 2 3 e(3G) = 2 3 e(H ◦ H ∪ H). (3) c(H ◦ H ∪ H) ≤ 1 = 1 3 e(H ◦ H ∪ H). (4) Since H ◦ H ∪ H is disconnected, the edges of H ◦ H ∪ H cannot be covered by two adjacent vertices. Applying Theorem 1.5, H◦H∪H is P3∪K2-decomposable and by construction it is G-decomposable. Thus both H ◦ H ◦ H and H ◦ H ∪ H are in LCM(P3 ∪ K2, G) and hence their least common multiple is not unique. Subcase (ii): lcm(P3 ∪ K2, G) = 2q. In this subcase there exists a graph H′ of size 2q which is both G and P3 ∪ K2 decomposable. We will prove that H ◦ H and H ∪ H are in LCM(P3 ∪ K2, G). (1) e(H ◦ H) = 2q ≡ 0 (mod 3), since e(H′) = 2q and H′ is P3 ∪ K2- decomposable. (2) In order to prove that ∆(H ◦H) ≤ 2 3 e(H ◦H), it is enough to prove that 2δ(H) ≤ 2 3 e(H ◦H). That is we need to prove δ(H) ≤ 1 3 (2q), where q = e(H) = e(G). CUBO 24, 1 (2022) On graphs that have a unique least common multiple 61 Suppose δ(H) > 2q 3 . Then 2q = ∑ v∈V (H) d(v) ≥ ∑ v∈V (H) δ(H) = nδ(H) > n( 2q 3 ) ⇒ n < 3. Since G is a disconnected graph without isolated vertices, n < 3 is not possible. Hence δ(H) ≤ 2q 3 . Thus ∆(H ◦ H) ≤ 2 3 e(H ◦ H). (3) c(H ◦ H) = 0 < 1 3 e(H ◦ H). (4) By the construction of H ◦H, the edges of H ◦H cannot be covered by two adjacent vertices. By Theorem 1.5, H ◦ H is P3 ∪ K2-decomposable and by construction, H ◦ H is G-decomposable and so H ◦ H ∈ LCM(P3 ∪ K2, G). Also H ∪ H ∈ LCM(P3 ∪ K2, G), since (1) e(H ∪ H) = 2q ≡ 0 (mod 3), since lcm(P3 ∪ K2) = 2q, where q = e(G) = e(H). (2) ∆(H ∪ H) ≤ ∆(H ◦ H) ≤ 2 3 e(H ◦ H) = 2 3 e(H ∪ H). (3) Here c(H ∪ H) ≤ 2. Thus c(H ∪ H) ≤ 1 3 e(H ∪ H) if 2 ≤ 2q 3 , that is if q ≥ 3, where, q = e(G) = e(H). Since G is a disconnected graph without isolated vertices, q 6= 1. Also if q = 2, then 2q = 4 6≡ 0 (mod 3). Thus in this subcase, q ≥ 3 and hence c(H ∪ H) ≤ 1 3 e(H ∪ H). Thus H ◦ H and H ∪ H belong to LCM(P3 ∪ K2, G) and hence their least common multiple is not unique. Acknowledgements The authors are thankful to Prof. M. I. Jinnah, formerly University of Kerala, India, for his suggestions during the preparation of this manuscript. The authors are also thankful to the anonymous reviewers for their careful reading and insightful comments for improving this work. 62 Reji T., Jinitha Varughese & Ruby R. CUBO 24, 1 (2022) References [1] 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. [2] 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. [3] N. Alon, “A note on the decomposition of graphs into isomorphic matchings”, Acta Math. Hungar., vol. 42, no. 3–4, pp. 221–223, 1983. [4] D. Bryant and B. Maenhaut, “Common multiples of complete graphs”, Proc. London Math. Soc. (3), vol. 86, no. 2, pp. 302–326, 2003. [5] 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. [6] 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. [7] G. Chartrand, C. M. Mynhardt and F. Saba, “On least common multiples of digraphs”, Utilitas Math., vol. 49, pp. 45–63, 1996. [8] Z.-C. Chen and T.-W. Shyu, “Common multiples of paths and stars”, Ars Combin., vol. 146, pp. 115–122, 2019. [9] O. Favaron, Z. Lonc and M. Truszczyński, “Decompositions of graphs into graphs with three edges”, Ars Combin., vol. 20, pp. 125–146, 1985. [10] 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. [11] 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. [12] 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. [13] C. Sunil Kumar, “Least common multiple of a cycle and a star”, Electron. Notes Discrete Math., vol. 15, pp. 204–206, 2003. [14] P. Wang, “On the sizes of least common multiples of stars versus cycles‘”, Util. Math., vol. 53, pp. 231–242, 1998. Introduction Main results On graphs that have a unique least common multiple with tK2 On graphs that have a unique least common multiple with P3 K2