Bireguláris gráf

A matematika, azon belül a gráfelmélet területén egy bireguláris gráf (biregular graph)[1] vagy félreguláris páros gráf (semiregular bipartite graph)[2] olyan páros gráf, melyben adott párosítás egy-egy oldalán az összes csúcs fokszáma megegyezik. Ha az -beli csúcsok fokszáma és a -beli csúcsoké , akkor a gráf -bireguláris.

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitívtávolságreguláriserősen reguláris
szimmetrikust-tranzitív, t ≥ 2ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláriséltranzitív
csúcstranzitívreguláris(ha páros)
bireguláris
Cayley-gráfzérószimmetrikusaszimmetrikus
A rombododekaéder élváza bireguláris.

PéldákSzerkesztés

Bármely   teljes páros gráf  -bireguláris.[3] A rombododekaéder (3,4)-bireguláris.[4]

CsúcsszámokSzerkesztés

Egy    -bireguláris gráfban teljesülnie kell a következő egyenlőségnek:  . Ez egyszerű kettős leszámlálásból következik:  -ban   db él végződik,  -ben pedig  , és az élek mindkét vége 1-1 csúccsal járul hozzá a fenti számokhoz.

SzimmetriaSzerkesztés

Minden reguláris páros gráf bireguláris. Minden éltranzitív gráf (nem tekintve az olyan gráfokat, melyekben izolált csúcsok vannak), ami nem csúcstranzitív, szükségképpen bireguláris.[3] Sőt, minden éltranzitív gráf reguláris vagy bireguláris.

KonfigurációkSzerkesztés

A geometriai konfigurációk illeszkedési gráfjai biregulárisak; egy bireguláris gráf pontosan akkor lehet egy absztrakt konfiguráció illeszkedési gráfja, ha girthparamétere legalább hat.[5]

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Biregular graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. Scheinerman, Edward R. & Ullman, Daniel H. (1997), Fractional graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons Inc., p. 137, ISBN 0-471-17864-0.
  2. Dehmer, Matthias & Emmert-Streib, Frank (2009), Analysis of Complex Networks: From Biology to Linguistics, John Wiley & Sons, p. 149, ISBN 9783527627998, <https://books.google.com/books?id=l9zURPH2GiUC&pg=PA149&lpg=PA149>.
  3. a b Lauri, Josef & Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037, <https://books.google.com/books?id=hsymFm0E0uIC&pg=PA20>.
  4. Réti, Tamás (2012), "On the relationships between the first and second Zagreb indices", MATCH Commun. Math. Comput. Chem. 68: 169–188, <http://www.pmf.kg.ac.rs/match/electronic_versions/match68/n1/match68n1_169-188.pdf>. Hozzáférés ideje: 2017-03-18 Archiválva 2017. augusztus 29-i dátummal a Wayback Machine-ben.
  5. Gropp, Harald (2007), "VI.7 Configurations", in Colbourn, Charles J. & Dinitz, Jeffrey H., Handbook of combinatorial designs (Second ed.), Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, pp. 353–355.