Primož Potočnik (Avtor), Pablo Spiga (Avtor), Gabriel Verret (Avtor)

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:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UP - Univerza na Primorskem
UDK: 519.1:512.54
COBISS: 1537132228 Povezava se bo odprla v novem oknu
ISSN: 0095-8956
Št. ogledov: 2835
Št. prenosov: 200
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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