Lexikografický součin grafů - Lexicographic product of graphs - Wikipedia

Lexikografický součin grafů.

v teorie grafů, lexikografický produkt nebo (graf) složení G ∙ H grafů G a H je graf takový, že

  • množina vrcholů G ∙ H je kartézský součin V (G) × V (H); a
  • libovolné dva vrcholy (u,proti) a (X,y) sousedí v G ∙ H jen a jen pokud u sousedí s X v G nebo u = X a proti sousedí s y vH.

Pokud jsou okrajové vztahy dvou grafů objednávkové vztahy, pak je hraniční vztah jejich lexikografického produktu odpovídající lexikografický řád.

Lexikografický produkt nejprve studoval Felix Hausdorff  (1914 ). Tak jako Feigenbaum & Schäffer (1986) Ukázalo se, že problém rozpoznání, zda je graf lexikografickým produktem, je ve složitosti ekvivalentní problému problém grafového izomorfismu.

Vlastnosti

Lexikografický produkt je obecně nekomutativní: G ∙ H ≠ H ∙ G. Splňuje však a distribuční právo s ohledem na disjunktní unii: (A + B) ∙ C = A ∙ C + B ∙ CKromě toho uspokojuje identitu s ohledem na doplňování: C(G ∙ H) = C (G) ∙ C (H). Zejména lexikografický produkt dvou samo-doplňkové grafy je samo-komplementární.

The číslo nezávislosti lexikografického produktu lze snadno vypočítat z faktorů jeho faktorů (Geller & Stahl 1975 ):

α (G ∙ H) = α (G) α (H).

The číslo kliky lexikografického produktu je také multiplikativní:

ω (G ∙ H) = ω (G) ω (H).

The chromatické číslo lexikografického produktu se rovná b-násobné chromatické číslo z G, pro b rovnající se chromatickému počtu H:

χ (G ∙ H) = χb(G), kde b = χ (H).

Lexikografickým součinem dvou grafů je a perfektní graf právě tehdy, jsou-li oba faktory dokonalé (Ravindra a Parthasarathy 1977 ).

Reference

  • Feigenbaum, J .; Schäffer, A. A. (1986), „Rozpoznávání složených grafů je ekvivalentní testování izomorfismu grafů“, SIAM Journal on Computing, 15 (2): 619–627, doi:10.1137/0215045, PAN  0837609.
  • Geller, D .; Stahl, S. (1975), „Chromatické číslo a další funkce lexikografického produktu“, Journal of Combinatorial Theory, Řada B, 19: 87–95, doi:10.1016/0095-8956(75)90076-3, PAN  0392645.
  • Hausdorff, F. (1914), Grundzüge der Mengenlehre, Lipsko
  • Imrich, Wilfried; Klavžar, Sandi (2000), Grafy produktů: Struktura a rozpoznáváníWiley, ISBN  0-471-37039-8
  • Ravindra, G .; Parthasarathy, K. R. (1977), „Perfect product graphs“, Diskrétní matematika, 20 (2): 177–186, doi:10.1016 / 0012-365X (77) 90056-5, hdl:10338.dmlcz / 102469, PAN  0491304.

externí odkazy