Egy gráf reguláris, ha minden csúcsának ugyanannyi szomszédja van, más szóval minden csúcs fokszáma azonos. A közös fokszámot k-val jelölve beszélhetünk k-reguláris gráfról is. A reguláris irányított gráfnak meg kell felelnie annak az erősebb feltételnek is, hogy az egyes csúcsokba bemenő élek és kimenő élek száma egyenlő legyen egymással.
Egy erősen reguláris gráf egy olyan reguláris gráf, ahol két összekötött csúcs közös szomszédainak a száma, illetve két össze nem kötött csúcs közös szomszédainak száma is független a két pont választásától.
A Nash-Williams-tétel szerint minden csúcsú k-reguláris gráfban van Hamilton-kör.
Egzisztencia Akkor és csak akkor létezik n csúcsú k-reguláris gráf, ha és páros. Ebben az esetben egy ilyen reguláris gráf könnyen megkonstruálható megfelelően paraméterezett cirkuláns gráfként.
Osztályozás A legfeljebb 2-reguláris gráfok egyszerűen osztályozhatóak. A 0-reguláris gráfok nem tartalmaznak éleket, ezek az üres gráfok. Az 1-reguláris gráfok egy-egy éllel összekötött csúcspárokat tartalmaznak. A 2-reguláris gráfok csúcsidegen körökből állnak. A 3-reguláris gráfokat angol nyelvterületen cubic graph-nak nevezik.
Algebrai tulajdonságok Legyen A egy gráf szomszédsági mátrixa.
A gráf akkor és csak akkor reguláris, ha sajátvektora A-nak.Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998. Ekkor a sajátérték k. A többi sajátértéknek megfelelő sajátvektorok merőlegesek -re, tehát az ilyen sajátvektorok koordinátáinak összege nulla.
Egy k-reguláris gráf csak akkor összefüggő, ha k egyszeres sajátértéke. A "csak akkor" meghatározás a Perron–Frobenius-tétel következménye.
Van egy másik kritérium a reguláris és összefüggő gráfokra: egy gráf pontosan akkor reguláris és összefüggő, ha az
mátrix eleme A szomszédsági algebrájának, azaz előáll A hatványainak lineáris kombinációjaként..
Legyen G k-reguláris gráf, D átmérővel és sajátértékekkel. Ha G nem páros gráf, akkor
Példák Minden teljes gráf (erősen) reguláris. Minden hiperkockagráf reguláris. Az egyenlő nagyságú osztályokkal rendelkező teljes páros gráfok regulárisak. Minden gyűrűs kocka 3-reguláris. A legkisebb reguláris, de nem erősen reguláris gráf a ciklusgráf és a hatcsúcsú körkörös gráf.
Generálás Létezik gyors algoritmus az adott fokszámú és csúcsszámú reguláris gráfok izomorfizmus erejéig való felsorolására.
Jegyzetek
Fordítás
Kapcsolódó szócikkek Erősen reguláris gráf Cage (gráfelmélet)
További információk
GenReg software and data by Markus Meringer.
Kategória:Reguláris gráfok Kategória:Gráfcsaládok