Povzetek
Slavni Tuttov izrek pravi, da je red vozliščnega stabilizatorja v povezanem 3-valentnem ločno-tranzitivnem grafu ne preseže vrednosti 48. Dolgo je bilo znano, da ta izrek ne velja v širšem kontekstu povezanih 3-valentnih vozliščno-tranzitivnih grafov. Znanih je bilo več družin takšnih grafov, v katerih red stabilizatorja raste eksponentno. V članku dokažemo presenetljiv rezultat, ki pravi, da je z izjemo teh dobro znanih družin, red vozliščnega stabilizatorja v povezanem 3-valentnem vozliščno tranzitivnem grafu omejen s sublinearno funkcijo reda grafa.
Ključne besede
valenca 3;valenca 4;točkovna tranzitivnost;ločna tranzitivnost;lokalno-diedrski;valency 3;valency 4;vertex-transitive;arc-transitive;locally-dihedral;
Podatki
Jezik: |
Angleški jezik |
Leto izida: |
2015 |
Tipologija: |
1.01 - Izvirni znanstveni članek |
Organizacija: |
UP - Univerza na Primorskem |
UDK: |
519.1:512.54 |
COBISS: |
1537132228
|
ISSN: |
0095-8956 |
Št. ogledov: |
2835 |
Št. prenosov: |
200 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Neznan jezik |
Sekundarni povzetek: |
A celebrated theorem of Tutte shows that the order of the vertex-stabiliser in a connected 3-valent arc-transitive graph does not exceed 48. It has long been known that no such bound exists in the broader context of connected 3-valent vertex-transitive graphs. In fact, several families of such graph in which the order of the vertex-stabiliser grows exponentially with the number of vertices were known. In this paper, we prove a surprising fact which shows that with the exception of these well understood families, in all other connected 3-valent vertex-transitive graphs the order of the vertex-stabiliser can be bounded above by a sublinear function of the order of the graph. The main result of this paper is that, if ▫$\Gamma$▫ is a connected 4-valent ▫$G$▫-arc-transitive graph and ▫$v$▫ is a vertex of ▫$\Gamma$▫, then either ▫$\Gamma$▫ is one of a well understood infinite family of graphs, or ▫$|G_v|\leq 2^43^6$▫ or ▫$2|G_v|\log_2(|G_v|/2)\leq |V\Gamma|$▫ and that this last bound is tight. As a corollary, we get a similar result for ▫$3$▫-valent vertex-transitive graphs. |
Vrsta dela (COBISS): |
Delo ni kategorizirano |
Strani: |
str. 148-180 |
Zvezek: |
ǂVol. ǂ111 |
Čas izdaje: |
2015 |
DOI: |
10.1016/j.jctb.2014.10.002 |
ID: |
9057969 |