Rooted product of graphs

In mathematical graph theory, the rooted product of a graph "G" and a rooted graph "H" is defined as follows: take |"V"("G")| copies of "H", and for every vertex $v\_i$ of "G", identify $v\_i$ with the root node of the "i"-th copy of "H".

More formally, assuming that "V"("G") = {"g"₁, ..., "g"_"n"}, "V"("H") = {"h"₁, ..., "h"_"m"} and that the root node of "H" is $h\_1$, define

:$G\; circ\; H\; :=\; (V,\; E)$

where

:$V\; =\; left\{(g\_i,\; h\_j):\; 1leq\; ileq\; n,\; 1leq\; jleq\; m\; ight\}$

and

:

If "G" is also rooted at "g"₁, one can view the product itself as rooted, at ("g"₁, "h"₁). The rooted product is a subgraph of the cartesian product of the same two graphs.

The rooted product is especially relevant for trees, as the rooted product of two trees is another tree. For instance, Koh et al. (1980) used rooted products to find graceful numberings for a wide family of trees.

References

*cite journal
author = Godsil, C. D.; McKay, B. D.
title = A new graph product and its spectrum
journal = Bull. Austral. Math. Soc.
volume = 18
year = 1978
issue = 1
pages = 21–28
id = MathSciNet | id = 0494910
url = http://cs.anu.edu.au/~bdm/papers/RootedProduct.pdf

*cite journal
author = Koh, K. M.; Rogers, D. G.; Tan, T.
title = Products of graceful trees
journal = Discrete Mathematics
volume = 31
year = 1980
issue = 3
pages = 279–292
id = MathSciNet | id = 0584121
doi = 10.1016/0012-365X(80)90139-9