Stark produkt av grafer

Kungens graf , en stark produkt av två väggrafer

I grafteorin är den starka produkten ett sätt att kombinera två grafer för att göra en större graf. Två hörn ligger intill varandra i den starka produkten när de kommer från par av hörn i faktorgraferna som är antingen intilliggande eller identiska. Den starka produkten är en av flera olika grafproduktoperationer som har studerats inom grafteorin. Den starka produkten av två grafer kan konstrueras som föreningen av två andra produkter av samma två grafer, den kartesiska produkten av grafer och tensorprodukten av grafer .

Ett exempel på en stark produkt är kungens graf , grafen över drag av en schackkung på ett schackbräde, som kan konstrueras som en stark produkt av bangrafer. Dekompositioner av plana grafer och relaterade grafklasser till starka produkter har använts som ett centralt verktyg för att bevisa många andra resultat om dessa grafer.

Försiktighet bör iakttas när man möter termen stark produkt i litteraturen, eftersom den också har använts för att beteckna grafernas tensorprodukt.

Definition och exempel

Den starka produkten G ⊠ H av graferna G och H är en graf så att vertexuppsättningen av G ⊠ H är den kartesiska produkten V ( G ) × V ( H ) ; och distinkta hörn ( u , u' ) och ( v , v' ) är intilliggande i G ⊠ H om och endast om :

u = v och u' gränsar till v' , eller

u' = v' och u gränsar till v , eller

u gränsar till v och u' gränsar till v' .

Det är föreningen av den kartesiska produkten och tensorprodukten .

Till exempel är kungens graf , en graf vars hörn är kvadrater på ett schackbräde och vars kanter representerar möjliga drag av en schackkung, en stark produkt av grafer med två vägar . Dess horisontella kanter kommer från den kartesiska produkten, och dess diagonala kanter kommer från tensorprodukten av samma två banor. Tillsammans utgör dessa två sorters kanter hela den starka produkten.

Egenskaper och applikationer

Varje plan graf är en subgraf av en stark produkt av en bana och en graf med trädbredd som högst sex. Detta resultat har använts för att bevisa att plana grafer har begränsat könummer , små universella grafer och koncisa närliggande märkningsscheman , och avgränsat icke-repetitivt kromatiskt tal och centrerat kromatiskt tal. Denna produktstruktur kan hittas i linjär tid . Utöver plana grafer har förlängningar av dessa resultat bevisats för grafer av begränsat släkte , grafer med en förbjuden moll som är en apexgraf , grafer med avgränsade grader med någon förbjuden moll och k-planära grafer .

Klicktalet för den starka produkten av två grafer är lika med produkten av klicknumren för de två graferna . Om två grafer båda har bounded twin-width , och dessutom en av dem har bounded grad, så har deras starka produkt också bounded twin-width.

En lövkraft är en graf som bildas av löv på ett träd genom att två löv görs intill varandra när deras avstånd i trädet är under någon tröskel k {\ $k}$ . Om $G$ är en $k$ -bladpotens av ett träd $T$ , så kan $T$ hittas som en subgraf av en stark produkt av $G$ med en $k$ -vertexcykel. Denna inbäddning har använts i igenkänningsalgoritmer för bladkrafter.

Den starka produkten av en 7-vertex cykelgraf och en 4-vertex komplett graf , $C_{7}\boxtimes K_{4}$ , har föreslagits som en möjlighet för en 10-kromatisk biplanar graf som skulle förbättra de kända gränserna för jord-månen problemet ; ett annat föreslaget exempel är grafen som erhålls genom att ta bort valfri vertex från $C_{5}\boxtimes K_{4}$ . I båda fallen är antalet hörn i dessa grafer mer än 9 gånger storleken på deras största oberoende uppsättning , vilket antyder att deras kromatiska antal är minst 10. Det är dock inte känt om dessa grafer är biplanära.