Kořenový produkt grafů - Rooted product of graphs

Kořenový produkt grafů.

V matematice teorie grafů, kořenový produkt a graf G a a zakořeněný graf H je definována takto: take |PROTI(G) | kopie Ha pro každý vrchol ${ displaystyle v_ {i}}$ z G, identifikovat ${ displaystyle v_ {i}}$ s kořenovým uzlem i-tá kopie H.

Více formálně, za předpokladu, že PROTI(G) = {G₁, ..., G_n}, PROTI(H) = {h₁, ..., h_m} a že kořenový uzel H je ${ displaystyle h_ {1}}$ , definovat

{ Displaystyle G Circ H: = (V, E)}

kde

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

a

{ displaystyle E = left {((g_ {i}, h_ {1}), (g_ {k}, h_ {1})) :( g_ {i}, g_ {k}) v 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 }}

Li G má také kořeny v G₁, lze samotný produkt zobrazit jako rootovaný, na (G₁, h₁). Kořenový produkt je a podgraf z kartézský součin stejných dvou grafů.

Aplikace

Kořenový produkt je obzvláště relevantní pro stromy, protože zakořeněný produkt dvou stromů je dalším stromem. Například Koh et al. (1980) k nalezení kořenových produktů ladné číslování pro širokou rodinu stromů.

Li H je kompletní graf se dvěma vrcholy K.₂, pak pro libovolný graf Gkořenový produkt G a H má dominantní číslo přesně polovinu svého počtu vrcholů. Každý propojený graf, ve kterém je číslo nadvlády poloviční než počet vrcholů, vzniká tímto způsobem, s výjimkou čtyř-vrcholů graf cyklu. Tyto grafy lze použít ke generování příkladů, ve kterých je vázán Vizingova domněnka, neprokázaná nerovnost mezi počtem dominancí grafů v jiném produktu grafů, kartézský součin grafů, je přesně splněno (Fink a kol. 1985 ). Jsou taky dobře pokryté grafy.

Reference

Godsil, C. D.; McKay, B. D. (1978), „Nový grafový produkt a jeho spektrum“ (PDF), Býk. Jižní. Matematika. Soc., 18 (1): 21–28, doi:10.1017 / S0004972700007760, PAN 0494910.
Fink, J. F .; Jacobson, M. S .; Kinch, L. F .; Roberts, J. (1985), „Na grafech, které mají dominantní číslo polovinu jejich pořadí“ Doba. Matematika. Hungar., 16 (4): 287–293, doi:10.1007 / BF01848079, PAN 0833264.
Koh, K. M .; Rogers, D. G .; Tan, T. (1980), „Výrobky ladných stromů“, Diskrétní matematika, 31 (3): 279–292, doi:10.1016 / 0012-365X (80) 90139-9, PAN 0584121.