Principal common divisors of graphs
type: Item
instance of: scholarly article
title: Principal common divisors of graphs
zbMATH Open document ID: 0781.05038
author: Gary Chartrand
author: Wayne Goddard
author: Michael A. Henning
author: Farrokh Saba
author: H. C. Swart
published in: European Journal of Combinatorics
publication date: 1993-05-16T00:00:00Z
review text: If a graph \(G\) is \(H\)-decomposable, then \(H\) is said to divide \(G\). 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 that divides both \(G_ 1\) and \(G_ 2\) then \(H\) divides \(G\). The authors determine several classes of graphs that are principal common divisors. In particular it is shown that (1) for \(n\geq 4\), the \(n\)-cycle \(C_ n\) is a principal common divisor, (2) for \(n\geq 2\), the path \(P_ n\) is a principal common divisor and (3) for \(n\geq 3\), \(K(2,n)\) is a principal common divisor. It is noted that \(K(3,3)\) is a principal common divisor but that it is not known which complete bipartite graphs \(K(m,n)\) where \(m,n \geq 3\) and \(m+n>6\) are principal common divisors. A connected graph \(G\) of order \(p\) and size \(q\) is called primal if \(q\) is prime and \(K_ p\) contains at least two edge-disjoint copies of \(G\). It is shown that every primal graph is a principal common divisor. Moreover, it is shown that every tree of prime size is a principal common divisor. A graph \(F\) is said to be a shadow divisor of a graph \(G\) if \(F\) does not divide \(G\), but if \(G\) divides \(H\) and \(H \neq G\), then \(F\) divides \(H\). It is shown that no graph having a shadow divisor is a principal common divisor. This result is used to show that no complete graph \(K_ n\), \(n \geq 3\), is a principal common divisor.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 168330
zbMATH Keywords: \(H\)-decomposable
zbMATH Keywords: principal common divisor
zbMATH Keywords: primal graph
zbMATH Keywords: shadow divisor
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
full work available at URL: eujc.1993.1012
OpenAlex ID: W2052667300
Wikidata QID: Q106064566
DOI: 10.1006/EUJC.1993.1012
description: scientific article; zbMATH DE number 168330