Rotprodukt

I grafteorin definieras rotprodukten av en graf G och en rotgraf H enligt följande: take | V ( G )| kopior av grafen H och för varje vertex av grafen G identifierar vi oss med rotpunkten för den i -te kopian av H .

Mer formell. Antag att V ( G ) = { g 1 , ..., g n }, V ( H ) = { h 1 , ..., h m } och att roten av grafen H är . Låt oss definiera produkten

,

var

och

Om grafen G också är rotad med rot g 1 kan man betrakta själva produkten som en rotad graf med rot ( g 1 , h 1 ). Rotprodukten är en subgraf av den direkta produkten av samma två grafer.

Applikationer

Rotprodukten är särskilt relevant för träd , eftersom rotprodukten från två träd återigen blir ett träd. Till exempel använde Koch et al (1980) rotprodukter för att hitta en graciös numrering för en bred familj av träd.

Om H är en komplett graf med två hörn K 2 , så har för varje graf G rotprodukten av graferna G och H ett dominanstal lika med exakt hälften av antalet av dess hörn. Varje sammankopplad graf där dominanstalet är lika med halva hörnen erhålls på detta sätt, förutom en cykel med fyra hörn. Dessa grafer kan användas för att generera exempel där en direkt grafprodukt når gränsen från Vizings gissning , en obevisad olikhet mellan dominansantalet av grafer i olika grafprodukter [1] .

Anteckningar

  1. ↑ Fink, Jacobson, Kinch, Roberts, 1985 .

Litteratur