On graphs that have a unique least commonMultiple

• Autores: Reiji Tomatsu, Jinitha Varughese, Ruby R.
• Localización: Cubo: A Mathematical Journal, ISSN 0716-7776, ISSN-e 0719-0646, Vol. 24, Nº. 1, 2022, págs. 53-62
• Idioma: inglés
• DOI: 10.4067/S0719-06462022000100053
• Enlaces
  • Texto completo
• Resumen
  • español

    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 disjuntas por ejes. El concepto fue introducido por G. Chartrand et al. donde ellos demostraron que cualquiera dos grafos no vacíos 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 caracterizamos los grafos que tienen un único mínimo común múltiplo con P3 ∪ K2.

  • English

    ABSTRACT A graph G without isolated vertices is a least common multiple 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 decomposition 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.

• Referencias bibliográficas
  • Adams, P.,Bryant, D.,Maenhaut, B.. (2004). Common multiples of complete graphs and a 4-cycle. Discrete Math.. 275. 289
  • Adams, P.,Bryant, D.,El-Zanati, S. I.,Vanden Eynden, C.,Maenhaut, B.. (2003). Least common multiples of cubes. Bull. Inst. Combin. Appl.....
  • Alon, N.. (1983). A note on the decomposition of graphs into isomorphic matchings. Acta Math. Hungar.. 42. 221
  • Bryant, D.,Maenhaut, B.. (2003). Common multiples of complete graphs. Proc. London Math. Soc.. 86. 302
  • Chartrand, G.,Holley, L.,Kubicki, G.,Schultz, M.. (1993). Greatest common divisors and least common multiples of graphs. Period. Math. Hungar.....
  • Chartrand, G.,Kubicki, G.,Mynhardt, C. M.,Saba, F.. (1997). On graphs with a unique least common multiple. Ars Combin.. 46. 177
  • Chartrand, G.,Mynhardt, C. M.,Saba, F.. (1996). On least common multiples of digraphs. Utilitas Math.. 49. 45-63
  • Chen, Z.-C.,Shyu, T.-W.. (2019). Common multiples of paths and stars. Ars Combin.. 146. 115
  • Favaron, O.,Lonc, Z.,Truszczyński, M.. (1985). Decompositions of graphs into graphs with three edges. Ars Combin.. 20. 125
  • Favaron, O.,Mynhardt, C. M. (1996). On the sizes of least common multiples of several pairs of graphs. Ars Combin.. 43. 181
  • Mynhardt, C. M.,Saba, F.. (1994). On the sizes of least common multiples of paths versus complete graphs. Utilitas Math.. 46. 117
  • Reji, T.. (2005). On graphs that have a unique least common multiple with matchings. Far East J. Appl. Math.. 18. 281
  • Sunil Kumar, C.. (2003). Least common multiple of a cycle and a star. Electron. Notes Discrete Math.. 15. 204
  • Wang, P.. (1998). On the sizes of least common multiples of stars versus cycles. Util. Math.. 53. 231