Tvådelad halva
I grafteorin är den tvådelade halva eller halva kvadraten av en tvådelad graf G = ( U , V , E ) en graf vars vertexuppsättning är en av de två sidorna av bipartitionen ( utan förlust av generalitet , U ) och i vilken det finns en kant u i u j för varje par av hörn u i , u j i U som ligger på två avstånd från varandra i G . Det vill säga, i en mer kompakt notation är den tvådelade halvan G 2 [ U ] där den upphöjda skriften 2 anger kvadraten på en graf och hakparenteserna anger en inducerad subgraf .
Exempel
Till exempel är den tvådelade halvan av den fullständiga tvådelade grafen Kn, n den av fullständiga grafen Kn och den tvådelade halvan hyperkubgrafen är den halverade kubgrafen . När G är en avståndsregelbunden graf är dess två tvådelade halvor båda avståndsregelbundna. Till exempel är den halverade Foster-grafen en av ändligt många grad-6 avstånd-reguljära lokalt linjära grafer .
Representation och hårdhet
Varje graf G är den tvådelade halvan av en annan graf, bildad genom att dela upp kanterna på G i tvåkantsbanor. Mer allmänt kan en representation av G som en tvådelad halva hittas genom att ta vilken klickkant som helst på G och ersätta varje klick med en stjärna . Varje representation uppstår på detta sätt. Eftersom det är NP-hårt att hitta det minsta klickkanttäcket, så är det också att hitta grafen med de minsta hörnen där G är den tvådelade halvan.
Speciella fall
Kartgraferna , det vill säga skärningsgraferna för inre-disjunkta enkelt sammankopplade områden i planet, är exakt de tvådelade halvorna av tvådelade plana grafer .