Abstract
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.
Keywords
valenca 3;valenca 4;točkovna tranzitivnost;ločna tranzitivnost;lokalno-diedrski;valency 3;valency 4;vertex-transitive;arc-transitive;locally-dihedral;
Data
Language: |
English |
Year of publishing: |
2015 |
Typology: |
1.01 - Original Scientific Article |
Organization: |
UP - University of Primorska |
UDC: |
519.1:512.54 |
COBISS: |
1537132228
|
ISSN: |
0095-8956 |
Views: |
2835 |
Downloads: |
200 |
Average score: |
0 (0 votes) |
Metadata: |
|
Other data
Secondary language: |
Unknown |
Secondary abstract: |
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. |
Type (COBISS): |
Not categorized |
Pages: |
str. 148-180 |
Issue: |
ǂVol. ǂ111 |
Chronology: |
2015 |
DOI: |
10.1016/j.jctb.2014.10.002 |
ID: |
9057969 |