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

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 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):