Produs rădăcină

În teoria grafurilor, produsul rădăcină al unui graf G și al unui graf rădăcină H este definit după cum urmează: ia | V ( G )| copii ale graficului H și pentru fiecare vârf al graficului G , ne identificăm cu vârful rădăcină al copiei i -a a lui H . $v_{i}$ $v_{i}$

Mai formal. Să presupunem că V ( G ) = { g 1 , ..., g n }, V ( H ) = { h 1 , ..., h m } și că rădăcina graficului H este . Să definim produsul $h_1$

G\circ H:=(V,E)

Unde

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

și

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

Dacă și graficul G este înrădăcinat cu rădăcina g 1 , se poate considera produsul în sine ca un grafic înrădăcinat cu rădăcină ( g 1 , h 1 ). Produsul rădăcină este un subgraf al produsului direct al acelorași două grafice.

Aplicații

Produsul rădăcină este deosebit de relevant pentru copaci , deoarece produsul rădăcină a doi copaci va fi din nou un copac. De exemplu, Koch și colaboratorii (1980) au folosit produse din rădăcină pentru a găsi o numerotare grațioasă pentru o familie largă de copaci.

Dacă H este un grafic complet cu două vârfuri K 2 , atunci pentru orice grafic G produsul rădăcină al graficelor G și H are un număr de dominanță egal cu exact jumătate din numărul vârfurilor sale. Orice graf conex în care numărul de dominanță este egal cu jumătate din vârfuri se obține în acest fel, cu excepția unui ciclu cu patru vârfuri. Aceste grafice pot fi folosite pentru a genera exemple în care un produs grafic direct atinge limita din conjectura Vizing , o inegalitate nedovedită între numărul de dominanță al graficelor în diferite produse grafice [1] .

Note

↑ Fink, Jacobson, Kinch, Roberts, 1985 .

Literatură

CD Godsil, BD McKay. Un nou produs grafic și spectrul său // Bull. Austral. Matematică. Soc .. - 1978. - T. 18 , nr. 1 . — S. 21–28 . - doi : 10.1017/S0004972700007760 .
JF Fink, MS Jacobson, LF Kinch, J. Roberts. Pe graficele care au numărul de dominație jumătate din ordinea lor // Perioada. Matematică. Ungaria.. - 1985. - T. 16 , nr. 4 . — S. 287–293 . - doi : 10.1007/BF01848079 .
KM Koh, DG Rogers, T. Tan. Produse ale copacilor grațioși // Matematică discretă . - 1980. - T. 31 , nr. 3 . — S. 279–292 . - doi : 10.1016/0012-365X(80)90139-9 .