A matematika, azon belül a gráfelmélet területén a G gráf és a H gyökeres gráf gyökeres szorzata egy gráfszorzás, olyan kétváltozósgráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. A G és H gyökeres szorzata olyan gráf, melyet a következő módon képzünk: vegyük H |V(G)| kópiáját, és G csúcsára azonosítjuk -t Hi-edik másolatának gyökércsúcsával.
Formálisabban, feltéve hogy V(G) = {g1, ..., gn}, V(H) = {h1, ..., hm} és H gyökere , legyen
ahol
és
Ha G is gyökeres g1 gyökérrel, akkor a szorzat maga is tekinthető gyökeres gráfnak, (g1, h1) gyökérrel. A gyökeres szorzat ugyanazon két gráf Descartes-szorzatánakrészgráfja.
Alkalmazások
A gyökeres szorzat különösen fák esetében érdekes, ahol két fa gyökeres szorzata egy harmadik fa. Például Koh et al. (1980) gyökeres szorzatok segítségével keresi meg nagyobb gráfcsaládok elegáns élcímkézéseit.
Ha H a K2 két csúcsú teljes gráf, akkor bármely G gráfra G és H gyökeres szorzatának dominálási száma éppen a csúcsok számának a fele. Minden összefüggő gráf, melynek dominálási száma a csúcsok számának fele ilyen módon előállítható, a C4körgráf kivételével. Ezek a gráfok alkalmasak olyan példák előállítására, melyekben a Vizing-sejtés (a dominálási szám és egy másik gráfszorzat, a Descartes-szorzat közötti bizonyítatlan egyenlőtlenség) korlátja éppen megvalósul (Fink et al. 1985). Ezek a gráfok továbbá jól fedett gráfok.
Fordítás
Ez a szócikk részben vagy egészben a Rooted product of graphs című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.