Kořenový produkt

V teorii grafů je kořenový součin grafu G a kořenového grafu H definován následovně: vzít | V ( G )| kopie grafu H a pro každý vrchol grafu G se ztotožňujeme s kořenovým vrcholem i -té kopie H . $v_{i}$ $v_{i}$

Formálnější. Předpokládejme, že V ( G ) = { g 1 , ..., g n }, V ( H ) = { h 1 , ..., h m } a že kořen grafu H je . Pojďme definovat produkt $h_1$

G\circ H:=(V,E)

kde

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

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})\v E(H)\vpravo\}

Pokud je i graf G odmocněn odmocninou g 1 , lze samotný součin považovat za odmocněný graf s odmocninou ( g 1 , h 1 ). Kořenový součin je podgrafem přímého součinu dvou stejných grafů.

Aplikace

Kořenový produkt je zvláště důležitý pro stromy , protože kořenový produkt dvou stromů bude opět strom. Například Koch a další (1980) použili kořenové produkty k nalezení elegantního číslování pro širokou rodinu stromů.

Je-li H úplný graf se dvěma vrcholy K 2 , pak pro libovolný graf G má kořenový součin grafů G a H číslo dominance rovné přesně polovině počtu jeho vrcholů. Tímto způsobem se získá jakýkoli souvislý graf, ve kterém se číslo dominance rovná polovině vrcholů, kromě cyklu se čtyřmi vrcholy. Tyto grafy lze použít ke generování příkladů, kdy přímý grafový součin dosáhne hranice z Vizingovy domněnky , což je neprokázaná nerovnost mezi počtem dominance grafů v různých grafových součinech [1] .

Poznámky

↑ Fink, Jacobson, Kinch, Roberts, 1985 .

Literatura

CD Godsil, BD McKay. Nový grafový produkt a jeho spektrum // Bull. Jižní. Matematika. Soc .. - 1978. - T. 18 , no. 1 . — S. 21–28 . - doi : 10.1017/S0004972700007760 .
JF Fink, MS Jacobson, LF Kinch, J. Roberts. Na grafech s nadvládou poloviční pořadí // Period. Matematika. Hungar.. - 1985. - T. 16 , no. 4 . — S. 287–293 . - doi : 10.1007/BF01848079 .
KM Koh, DG Rogers, T. Tan. Produkty půvabných stromů // Diskrétní matematika . - 1980. - T. 31 , no. 3 . — S. 279–292 . - doi : 10.1016/0012-365X(80)90139-9 .