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

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:
Typology: 1.01 - Original Scientific Article
Organization: UP - University of Primorska
UDC: 519.1:512.54
COBISS: 1537132228 Link will open in a new window
ISSN: 0095-8956
Views: 2835
Downloads: 200
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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