Gyökértermék

A gráfelméletben egy G gráf és egy H gyökgráf gyökérszorzatát a következőképpen definiáljuk: vegye | V ( G )| a H gráf másolatai és a G gráf minden csúcsára azonosulunk H i - edik másolatának gyökércsúcsával . $v_{i}$ $v_{i}$

Hivatalosabb. Tegyük fel, hogy V ( G ) = { g 1 , ..., g n }, V ( H ) = { h 1 , ..., h m }, és a H gráf gyöke . Határozzuk meg a terméket $h_1$

G\circ H:=(V,E)

ahol

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

é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)\jobbra\}

Ha a G gráf is gyökerezve van g 1 gyökkel , akkor magát a szorzatot tekinthetjük gyökér gráfnak ( g 1 , h 1 ). A gyökérszorzat ugyanazon két gráf közvetlen szorzatának részgráfja .

Alkalmazások

A gyökértermék különösen fontos a fák számára , mivel két fa gyökérterméke ismét egy fa lesz. Például Koch és munkatársai (1980) gyökértermékeket használtak, hogy kecses számozást találjanak egy széles facsalád számára.

Ha H egy teljes gráf két K 2 csúcsponttal , akkor bármely G gráf esetén a G és H gráfok gyökérszorzatának dominanciája pontosan a csúcsok számának a felével egyenlő. Minden olyan összefüggő gráfot kapunk, amelyben a dominanciaszám egyenlő a csúcsok felével, kivéve a négy csúcsú ciklust . Ezek a gráfok használhatók olyan példák generálására, ahol a közvetlen gráfszorzat eléri a határt a Vizing -sejtésből , ami egy nem igazolt egyenlőtlenség a különböző gráftermékekben lévő gráfok dominanciája között [1] .

Jegyzetek

↑ Fink, Jacobson, Kinch, Roberts, 1985 .

Irodalom

CD Godsil, BD McKay. Egy új gráftermék és spektruma // Bull. Délvidéki. Math. Soc .. - 1978. - T. 18 , 1. sz. 1 . – S. 21–28 . - doi : 10.1017/S0004972700007760 .
JF Fink, MS Jacobson, LF Kinch, J. Roberts. Azokon a grafikonokon, amelyek dominanciája a sorrend fele // Period. Math. Magyar.. - 1985. - T. 16 , sz. 4 . – S. 287–293 . - doi : 10.1007/BF01848079 .
KM Koh, DG Rogers, T. Tan. Kecses fák termékei // Diszkrét matematika . - 1980. - T. 31 , sz. 3 . – S. 279–292 . - doi : 10.1016/0012-365X(80)90139-9 .