Szimmetrikus gráf

A matematika, azon belül a gráfelmélet területén egy G gráf akkor szimmetrikus vagy ívtranzitív (symmetric / arc-transitive) ha G bármely két, u₁—v₁ és u₂—v₂ csúcsszomszéd-párjára létezik olyan automorfizmus,

f : V(G) → V(G),

melyre

f(u₁) = u₂ és f(v₁) = v₂.^[1]

Más szavakkal egy gráf akkor szimmetrikus, ha automorfizmus-csoportja tranzitívan hat szomszédos csúcsok rendezett párjaira (tehát olyan éleken, melyeknek irányt tulajdonítunk).^[2] Az ilyen gráfot néha 1-arc-transitive („1-ív-tranzitív”)^[2] vagy flag-transitive néven is leírják.^[3]

A definíció alapján egy izolált csúcsok nélküli szimmetrikus gráfnak csúcstranzitívnak is kell lennie.^[1] Mivel a fenti definíció egy élt egy másikba visz át, a(z összefüggő) szimmetrikus gráfok szükségképpen é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áfok például éltranzitívak és 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.^[3] 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.^[4] Ezek a féltranzitív gráfok.^[5] A legkisebb összefüggő féltranzitív a 4 fokszámú, 27 csúcsú Holt-gráf.^[1]^[6] 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áfokná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.^[1]

Egy t-ív (t-arc) t+1 csúcs olyan sorozata, melyben bármely két egymást követő csúcs szomszédos, és az ismétlődő csúcsok mindig 2-nél nagyobb távolságra vannak. Egy t-tranzitív gráf vagy t-ívtranzitív gráf (t-transitive graph, t-arc-transitive graph) olyan gráf, melynek automorfizmus-csoportja tranzitíven hat a t-ívekre, de (t+1)-ívekre nem. Mivel az 1-ívek egyszerűen a gráf élei, ezért minden legalább 3 fokszámú szimmetrikus gráf t-tranzitív valamely t-re, t értéke segítségével pedig osztályozni lehet a szimmetrikus gráfokat. A kocka például 2-tranzitív.^[1]

Példák

A szimmetriafeltételt a 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.^[7] Az első Foster censust 1930-ban kezdte meg az akkor a Bell Labsnál dolgozó Ronald M. Foster,^[8] 1988-ban (amikor Foster 92 éves volt^[1]) 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.^[9] 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^[10]^[11] (ezek közül tíz egyben távolságtranzitív is, a kivételeket jelezzük):

Csúcsok	Átmérő	Girth	Gráf	Megjegyzés
4	1	3	A K₄ teljes gráf	távolságtranzitív, 2-tranzitív
6	2	4	A K_3,3 teljes páros gráf	távolságtranzitív, 3-tranzitív
8	3	4	A kocka csúcsai és élei	távolságtranzitív, 2-tranzitív
10	2	5	A Petersen-gráf	távolságtranzitív, 3-tranzitív
14	3	6	A Heawood-gráf	távolságtranzitív, 4-tranzitív
16	4	6	A Möbius–Kantor-gráf	2-tranzitív
18	4	6	A Papposz-gráf	távolságtranzitív, 3-tranzitív
20	5	5	A dodekaéder csúcsai és élei	távolságtranzitív, 2-tranzitív
20	5	6	A Desargues-gráf	távolságtranzitív, 3-tranzitív
24	4	6	A Nauru-gráf (a G(12,5) általánosított Petersen-gráf)	2-tranzitív
26	5	6	Az F26A-gráf^[11]	1-tranzitív
28	4	7	A Coxeter-gráf	távolságtranzitív, 3-tranzitív
30	4	8	A Tutte–Coxeter-gráf	távolságtranzitív, 5-tranzitív

További ismert 3-reguláris szimmetrikus gráfok a Dyck-gráf, a Foster-gráf és a Biggs–Smith-gráf. A fenti tíz távolságtranzitív gráfon, továbbá a Foster-gráfon és a Biggs–Smith-gráfon kívül nem létezik több 3-reguláris távolságtranzitív gráf. A nem 3-reguláris szimmetrikus gráfok közé tartoznak a körgráfok (fokszám: 2), a teljes gráfok (fokszám>3), hiperkockagráfok (fokszám>3), valamint az oktaéder, ikozaéder, a kuboktaéder és az ikozidodekaéder gráfjai. A Rado-gráf példa a végtelen számú csúccsal és fokszámmal rendelkező szimmetrikus gráfra.

Tulajdonságok

Egy szimmetrikus gráf mindig d-szeresen összefüggő, ahol d a fokszám.^[3] Csúcstranzitív gráfokról általában csak annyi mondható el, hogy összefüggőségük alsó korlátja 2(d+1)/3.^[2] Egy legalább 3 fokszámú t-tranzitív gráf girthe legalább 2(t–1). Nem létezik viszont véges, legalább 3 fokszámú t-tranzitív gráf a t ≥ 8 értékekre. Ha a fokszám pontosan 3, akkor már t ≥ 6-ra sem.

Kapcsolódó szócikkek

Algebrai gráfelmélet

Fordítás

Ez a szócikk részben vagy egészben a Symmetric graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ ^a ^b ^c ^d ^e ^f Biggs, Norman. Algebraic Graph Theory, 2nd, Cambridge: Cambridge University Press, 118–140. o. (1993). ISBN 0-521-45897-8
↑ ^a ^b ^c Algebraic Graph Theory. New York: Springer, 59. o. (2001). ISBN 0-387-95220-9
↑ ^a ^b ^c Babai, L. Handbook of Combinatorics. Elsevier (1996)
↑ Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
↑ Handbook of Graph Theory. CRC Press, 491. o. (2004). ISBN 1-58488-090-2
↑ Holt, Derek F. (1981). „A graph which is edge transitive but not arc transitive”. Journal of Graph Theory 5 (2), 201–204. o. DOI:10.1002/jgt.3190050210. .
↑ Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
↑ Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.
↑ "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
↑ Biggs, p. 148
↑ ^a ^b Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.

További információk

Cubic symmetric graphs (The Foster Census). Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
Trivalent (cubic) symmetric graphs on up to 2048 vertices. Marston Conder, August 2006, retrieved 2009-08-20.

Matematikaportál • összefoglaló, színes tartalomajánló lap

[biggs-1] ↑ ^a ^b ^c ^d ^e ^f Biggs, Norman. Algebraic Graph Theory, 2nd, Cambridge: Cambridge University Press, 118–140. o. (1993). ISBN 0-521-45897-8

[godsil-2] Algebraic Graph Theory. New York: Springer, 59. o. (2001). ISBN 0-387-95220-9

[babai-3] Babai, L. Handbook of Combinatorics. Elsevier (1996)

[4] Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.

[handbook-5] Handbook of Graph Theory. CRC Press, 491. o. (2004). ISBN 1-58488-090-2

[6] Holt, Derek F. (1981). „A graph which is edge transitive but not arc transitive”. Journal of Graph Theory 5 (2), 201–204. o. DOI:10.1002/jgt.3190050210. .

[7] Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63

[8] Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.

[9] "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

[10] Biggs, p. 148

[F26A-11] Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	${\boldsymbol {\rightarrow }}$	távolságreguláris	${\boldsymbol {\leftarrow }}$	erősen reguláris
${\boldsymbol {\downarrow }}$
szimmetrikus	${\boldsymbol {\leftarrow }}$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
${\boldsymbol {\downarrow }}$
_{(ha összefüggő)} csúcs- és éltranzitív	${\boldsymbol {\rightarrow }}$	éltranzitív és reguláris	${\boldsymbol {\rightarrow }}$	éltranzitív
${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$
csúcstranzitív	${\boldsymbol {\rightarrow }}$	reguláris	${\boldsymbol {\rightarrow }}$	_(ha páros) bireguláris
${\boldsymbol {\uparrow }}$
Cayley-gráf	${\boldsymbol {\leftarrow }}$	zérószimmetrikus		aszimmetrikus