A matematika, azon belül a gráfelmélet területén a G és H gráfok lexikografikus szorzata vagy gráfkompozíció egy gráfszorzás, olyan kétváltozós gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. A vagy lexikografikus szorzat olyan gráf, melyre a következők igazak: csúcshalmaza megegyezik a Descartes-szorzattal; két -beli csúcs, és pontosan akkor szomszédosak, ha szomszédos -szel -ben vagy és szomszédos -nal -ban.
Ha a két gráf élrelációi rendezési relációk, akkor lexikografikus szorzatuk élrelációja éppen a megfelelő lexikografikus rendezés.
A lexikografikus szorzatot elsőként tanulmányozta. Ahogy megmutatta, annak eldöntése, hogy egy gráf lexikografikus szorzatként előáll-e, a gráfizomorfizmus-problémával ekvivalens.
Tulajdonságok A lexikografikus szorzat általában nemkommutatív: . A diszjunkt unió művelettel együtt azonban disztributívak: . Ezen kívül teljesít egy a komplementerképzéssel kapcsolatos azonosságot: .
A lexikografikus szorzat függetlenségi száma könnyen adódik tényezőinek függetlenségi számaiból : .
A lexikografikus szorzat klikkszáma is multiplikatív: .
A lexikografikus szorzat kromatikus száma megegyezik G frakcionális színezés szerinti b-szeres kromatikus számával, ahol b megegyezik H kromatikus számával: , ahol b χ(H).
Két gráf lexikografikus szorzata pontosan akkor perfekt gráf, ha mindkét tényező perfekt .
Fordítás
Jegyzetek . .
.
További információk
Kategória:Gráfszorzatok