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

a
gondolatjel javítása (checkwiki [050]) AWB
[ellenőrzött változat][ellenőrzött változat]
a (kisbetűvel nem működik)
a (gondolatjel javítása (checkwiki [050]) AWB)
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&ndash;237231–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|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" />
 
 
==Példák==
A szimmetriafeltételt a [[3-reguláris gráf|3-regularitás]] elvárásával társítva már kellően erős feltételt kapunk ahhoz, hogy ezeket a ritka gráfokat listázni legyen érdemes. A '''Foster census''' („Foster-féle népszámlálás”) és kiterjesztései ilyen listákat hoztak létre.<ref>[[Marston Conder]], ''[http://www.math.auckland.ac.nz/~conder/preprints/cubic768.ps Trivalent symmetric graphs on up to 768 vertices],'' J. Combin. Math. Combin. Comput, vol. 20, pp. 41&ndash;6341–63</ref> Az első Foster censust 1930-ban kezdte meg az akkor a [[Bell Labs]]nál dolgozó [[R. M. Foster|Ronald M. Foster]],<ref>Foster, R. M. "Geometrical Circuits of Electrical Networks." ''[[Transactions of the American Institute of Electrical Engineers]]'' '''51''', 309&ndash;317309–317, 1932.</ref> 1988-ban (amikor Foster 92 éves volt<ref name="biggs"/>) az akkori naprakész Foster census eredményeit (512 csúcsig az összes 3-reguláris szimmetrikus gráfot) könyv formájában is kiadták.<ref>"The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) {{ISBN|0-919611-19-2}}</ref> A következő listában a Foster census első tizenhárom eleme szerepel, avagy a legfeljebb 30 csúcsú 3-reguláris szimmetrikus gráfok<ref>Biggs, p. 148</ref><ref name="F26A">Weisstein, Eric W., "[http://mathworld.wolfram.com/CubicSymmetricGraph.html Cubic Symmetric Graph]", from Wolfram MathWorld.</ref> (ezek közül tíz egyben [[távolságtranzitív gráf|távolságtranzitív]] is, a kivételeket jelezzük):
 
{| class="wikitable"
71 397

szerkesztés