„Szimmetrikus gráf” változatai közötti eltérés

Link hozzáadása egy könyvforráshoz az ellenőrizhetőségért (20211021sim)) #IABot (v2.0.8.2) (GreenC bot
[ellenőrzött változat][ellenőrzött változat]
(Adjon hozzá 1 könyvet a forráshoz (20210114)) #IABot (v2.0.7) (GreenC bot)
(Link hozzáadása egy könyvforráshoz az ellenőrizhetőségért (20211021sim)) #IABot (v2.0.8.2) (GreenC bot)
 
A definíció alapján egy izolált csúcsok nélküli szimmetrikus gráfnak [[csúcstranzitív gráf|csúcstranzitívnak]] is kell lennie.<ref name="biggs" /> Mivel a fenti definíció egy élt egy másikba visz át, a(z összefüggő) szimmetrikus gráfok szükségképpen [[éltranzitív gráf|éltranzitívak]] is. Egy éltranzitív gráf azonban nem feltétlenül szimmetrikus, hiszen előfordulhat, hogy ''a''—''b''-t átviszi ''c''—''d''-be, de ''d''—''c''-be nem. A [[félszimmetrikus gráf]]ok például éltranzitívak és [[reguláris gráf|regulárisak]], de nem csúcstranzitívak.
 
Minden összefüggő szimmetrikus gráf tehát csúcs- és éltranzitív egyszerre, páratlan fokszámú gráfokra ennek a megfordítása is igaz.<ref name="babai" /> A páros fokszámú gráfok között azonban léteznek olyan él- és csúcstranzitív összefüggő gráfok, melyek nem szimmetrikusak.<ref>Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.</ref> Ezek a [[féltranzitív gráf]]ok.<ref name="handbook">{{cite book |author1=Gross, J.L. |author2=Yellen, J. |lastauthoramp=yes | title=Handbook of Graph Theory | publisher=CRC Press | year=2004| page=491 | isbn=1-58488-090-2}}</ref> A legkisebb összefüggő féltranzitív a 4 fokszámú, 27 csúcsú [[Holt-gráf]].<ref name="biggs" /><ref>{{Cite journal|title=A graph which is edge transitive but not arc transitive|url=https://archive.org/details/sim_journal-of-graph-theory_summer-1981_5_2/page/201|first=Derek F.|last=Holt|journal=Journal of Graph Theory|volume=5|issue=2|pages=201–204|year=1981|doi=10.1002/jgt.3190050210}}.</ref> Egyes szerzők félreérthető módon a „szimmetrikus gráf” kifejezést az összes csúcs- és éltranzitív gráfra használják, nem csak az ívtranzitív gráfokra – ez a definíció a féltranzitív gráfokat is magába foglalná.
A [[távolságtranzitív gráf]]oknál az automorfizmusnál nem szomszédos (tehát 1 távolságra lévő) csúcspárokat, hanem megegyező távolságra lévő két csúcspárt veszükn figyelembe. Az ilyen gráfok a definíció alapján autommatikusan szimmetrikusak is.<ref name="biggs" />
 
320 103

szerkesztés