Greatest common divisors and least common multiples of graphs |
| |
| Authors: | G Chartrand L Holley G Kubicki M Schultz |
| |
| Institution: | (1) Department of Mathematics and Statistics, Western Michigan University, 49008-5152 Kalamazo, Michigan, USA;(2) Louisville |
| |
| Abstract: | A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG
1 andG
2 ifG is a graph of maximum size for whichG|G
1 andG|G
2, while a graphH without isolated vertices is a least common multiple ofG
1 andG
2 ifH is a graph of minimum size for whichG
1|H andG
2|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG
1 andG
2 to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG
1,G
2 of graphs are determined, including when one ofG
1 andG
2 is a cycle of even length and the other is a star.G. C's research was supported in part by the Office of Naval Research, under Grant N00014-91-I-1060 |
| |
| Keywords: | Primary 05C70 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
