Gráfok gyökeres szorzata

Gráfok gyökeres szorzata.

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ós grá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 $v_{i}$ csúcsára azonosítjuk $v_{i}$-t H i-edik másolatának gyökércsúcsával.

Formálisabban, feltéve hogy V(G) = {g₁, ..., g_n}, V(H) = {h₁, ..., h_m} és H gyökere $h_{1}$, legyen

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

ahol

$V=\left\{(g_{i},h_{j}):1\leq i\leq n,1\leq j\leq m\right\}$

és

$E=\left\{((g_{i},h_{1}),(g_{k},h_{1})):(g_{i},g_{k})\in E(G)\right\}\cup \bigcup _{i=1}^{n}\left\{((g_{i},h_{j}),(g_{i},h_{k})):(h_{j},h_{k})\in E(H)\right\}$

Ha G is gyökeres g₁ gyökérrel, akkor a szorzat maga is tekinthető gyökeres gráfnak, (g₁, h₁) gyökérrel. A gyökeres szorzat ugyanazon két gráf Descartes-szorzatának ré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 K₂ 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 C₄ kö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.

Jegyzetek

• Godsil, C. D. & McKay, B. D. (1978), "A new graph product and its spectrum", Bull. Austral. Math. Soc. 18 (1): 21–28, doi:10.1017/S0004972700007760, <http://cs.anu.edu.au/~bdm/papers/RootedProduct.pdf>.
• Fink, J. F.; Jacobson, M. S. & Kinch, L. F. et al. (1985), "On graphs having domination number half their order", Period. Math. Hungar. 16 (4): 287–293, DOI 10.1007/BF01848079.
• Koh, K. M.; Rogers, D. G. & Tan, T. (1980), "Products of graceful trees", Discrete Mathematics 31 (3): 279–292, DOI 10.1016/0012-365X(80)90139-9.