A matematika, azon belül a gráfelmélet területén a Henson-gráf az irányítatlan végtelen gráfok közül az az egyedi, megszámlálható homogén gráf, ami nem tartalmaz -csúcsú klikket, de tartalmazza az összes -mentes véges gráfot feszített részgráfként. Például a olyan háromszögmentes gráf, ami tartalmazza az összes véges háromszögmentes gráfot.
A gráfok névadója C. Ward Henson, aki 1971-ben megadta az előállításuk módját (minden -ra).. A Henson-gráfok közül az elsőt, a -at homogén háromszögmentes gráfnak vagy az univerzális háromszögmentes gráfnak is nevezik.
Konstrukció A gráfok megszerkesztése során Henson a Rado-gráf csúcsait úgy rendezi sorba, hogy a csúcsok bármely véges halmazához végtelen sok olyan csúcs tartozzon, melyeknek a korábbi szomszédaik halmaza (az ilyen sorozatok létezése a Rado-gráf egyedi jellemzője). Ezután úgy definiálja -t, mint a Rado-gráf feszített részgráfját, amit annak minden -klikkjének (a sorba rendezés szerinti) utolsó csúcsának eltávolításával kapunk.
Ezzel a konstrukcióval minden gráf a feszített részgráfja, és a feszített részgráfok ezen láncának uniója éppen a Rado-gráf. Mivel minden gráfból a Rado-gráf minden -klikkjének legalább egy csúcsa hiányzik, ezért nem szerepel -klikk a -ben.
Univerzalitás Bármely véges vagy megszámlálhatóan végtelen -klikkmentes gráf megtalálható feszített részgráfjaként, csúcsonként felépítve – minden lépésben azt a csúcsot adva hozzá, melynek korábbi -beli szomszédai megfelelnek a hozzá tartozó -beli csúcs korábbi szomszédainak halmazával. Más szóval, az -klikkmentes gráfok családjának univerzális gráfja.
Mivel léteznek tetszőlegesen magas kromatikus számú -klikkmentes gráfok, ezért a Henson-gráfok kromatikus száma végtelen. Ennél erősebb állítás, hogy ha egy Henson-gráfot véges számú feszített részgráfra particionálunk, akkor ezen részgráfok közül legalább egy tartalmazza az összes -klikkmentes véges gráfot feszített részgráfjaként.
Szimmetria A Rado-gráfhoz hasonlóan a tartalmaz kétirányú Hamilton-utat, melyre igaz, hogy az út bármely szimmetriája az egész gráf szimmetriája is. Ez nem igaz azonban általában a gráfokra, ha : ezekben a gráfokban a gráf minden automorfizmusának egynél több pályája van.
Fordítás
Jegyzetek
Kategória:Parametrikus gráfcsaládok Kategória:Végtelen gráfok