Principal Common Divisors of Graphs

✍ Scribed by Gary Chartrand; Wayne Goddard; Michael A. Henning; Farrokh Saba; Henda C. Swart

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 261 KB
• Volume: 14
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.1993.1012

✦ Synopsis

A graph (H) divides a graph (G), written (H \mid G), if (G) is (H)-decomposable. If (H \neq G), then (H) properly divides (G). A graph (G) is a principal common divisor if there exist graphs (G_{1}) and (G_{2}) such that (G) properly divides (G_{1}) and (G_{2}), and if (H) is any graph such that (H \mid G_{1}) and (H \mid G_{2}), then (H \mid G). Several graphs that are principal common divisors are described. It is shown that complete graphs are not principal common divisors.