Bivariegovaný graf - Bivariegated graph - Wikipedia

v teorie grafů, a dvojrozměrný graf je graf, jehož množina vrcholů může být rozdělené na dvě stejné části tak, aby každý vrchol sousedil s přesně jedním vrcholem z druhé množiny, která jej neobsahuje.[1][2][3]V bivarigovaném grafu G s 2n vrcholy, existuje sada n nezávislé hrany tak, že žádný lichý počet z nich neleží na cyklu G.

Příklady

The Petersenův graf, zobrazený níže, je bivariegovaný graf: pokud jej jeden rozdělíme na vnější pětiúhelník a vnitřní pětibodovou hvězdu, každý vrchol na jedné straně oddílu má přesně jednoho souseda na druhé straně oddílu. Obecněji to platí pro všechny zobecněný Petersenův graf vytvořený spojením vnějšího mnohoúhelníku a vnitřní hvězdy se stejným počtem bodů; například to platí pro Möbius – Kantorův graf a Desargues graf.

Petersen1 tiny.svg

Žádný hyperkrychlový graf, jako je čtyřrozměrná hyperkrychle zobrazená níže, je také dvojrozměrná.

Hypercubecentral.svg

Níže zobrazený graf však není dvojrozměrný. Ať už si vyberete tři nezávislé hrany, jedna z nich je hranou cyklu.

6n-graf.svg

Bivariegated stromy

Strom T s 2n vrcholy, je bivariegated právě tehdy, když číslo nezávislosti z T je n, nebo ekvivalentně, pokud a pouze pokud má perfektní shoda.[1]

Zobecnění

The k-varigovaný graf, k ≥ 3, lze definovat podobně. Říká se, že je graf k-varigováno, pokud lze jeho sadu vrcholů rozdělit na k stejné části tak, že každý vrchol sousedí s přesně jedním vrcholem ze všech ostatních částí, které jej neobsahují.[2]

Poznámky

  • Charakterizující stupně bivariegated grafů byl nevyřešený problém v teorii grafů.
  1. ^ A b Bednarek & Sanders (1973).
  2. ^ A b Bhat-Nayak, Choudum a Naik (1978).
  3. ^ Riddle (1978).

Reference

  • Bednarek, A. R .; Sanders, E. L. (1973), „Charakterizace dvourozměrných stromů“, Diskrétní matematika, 5: 1–14, doi:10.1016 / 0012-365X (73) 90022-8.
  • Bhat-Nayak, Vasanti N.; Choudum, S.A.; Naik, Ranjan N. (1978), „Charakterizace 2-pestrých grafů a 3-pestrých grafů“, Diskrétní matematika, 23: 17–22, doi:10.1016 / 0012-365X (78) 90182-6.
  • Bhat-Nayak, Vasanti N.; Kocay, W. L.; Naik, Ranjan N. (1980), "Násilně 2-pestré stupně", Utilitas Math., 18: 83–89.
  • Bhat-Nayak Vasanti N., Ranjan N. Naik, Další výsledky na 2-pestrých grafech, Utilitas Math. 12 (1977) 317–325.
  • Javdekar, Medha (1980), „Charakterizace násilně k- pestré stupně, k ≥ 3", Diskrétní matematika, 29 (1): 33–38, doi:10.1016 / 0012-365X (90) 90284-O.
  • Javdekar, Medha (1980), „Charakterizace k- pestré grafy, k ≥ 3", Diskrétní matematika, 32 (3): 263–270, doi:10.1016 / 0012-365X (80) 90264-2
  • Riddle, Fay A. (1978), Bivariegované grafy a jejich izomorfismy, Ph.D. disertační práce, University of Florida.