Principal common divisors of graphs

Gary Chartrand, Wayne Goddard, Michael A. Henning, Farrokh Saba, Henda C. Swart

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


A graph H divides a graph G, written H | G, if G is H-decomposable. If H ≠ G, then H properly divides G. A graph G is a principal common divisor if there exist graphs G1 and G2 such that G properly divides G1 and G2, and if H is any graph such that H | G1 and H | G2, then H | G. Several graphs that are principal common divisors are described. It is shown that complete graphs are not principal common divisors.

Original languageEnglish
Pages (from-to)85-93
Number of pages9
JournalEuropean Journal of Combinatorics
Issue number2
Publication statusPublished - Mar 1993
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Principal common divisors of graphs'. Together they form a unique fingerprint.

Cite this