Principal common divisors of graphs (Q1209724)

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.