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=\{(g_i,h_j):1\le i\le n,1\le j\le m\}$

és

$E=\{((g_i,h_1),(g_k,h_1)):(g_i,g_k)\in E(G)\}\cup \bigcup _{i=1}^n\{((g_i,h_j),(g_i,h_k)):(h_j,h_k)\in E(H)\}$

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.