Common Multiples of Paths and Stars with Crowns
DOI:
https://doi.org/10.22199/issn.0717-6279-5720Keywords:
Graph Decomposition, Common Multiples of Graphs, Path, Star, CrownAbstract
{\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.
}
References
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.
Published
How to Cite
Issue
Section
Copyright (c) 2024 Saritha Chandran C, Reji T
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
