3-valentni vozliščno tranzitivni grafi

delo diplomskega seminarja

Teja Škvarč (Author), Primož Potočnik (Mentor)

Abstract

Cilj diplomskega dela je določiti vse kubične vozliščno tranzitivne grafe do nekega v naprej danega reda. $G$-vozliščno tranzitivni graf je graf, za katerega velja, da podgrupa $G$ grupe avtomorfizmov grafa deluje tranzitivno na množico vozlišč. Glede na število orbit delovanja vozliščnega stabilizatorja $G_v$ na soseščini $\Gamma(v)$ ločimo tri skupine kubičnih vozliščno tranzitivnih grafov. Prvo skupino, kjer imamo samo eno orbito, nam trditev, ki pravi, da ima delovanje vozliščnega stabilizatorja na soseščini enako orbit kot delovanje grupe $G$ na lokih grafa, poveže s kubičnimi ločno tranzitivnimi grafi. Drugo skupino, kjer imamo tri orbite, nam Sabidussijev izrek poveže s Cayleyjevimi grafi. Tretjo skupino, kjer imamo dve orbiti, pa povežemo s tetravalentnimi ločno tranzitivnimi grafi.

Keywords

matematika;kubični grafi;vozliščno tranzitivni grafi;ločno tranzitivni grafi;delovanje grupe na množico;stabilizator;orbite;avtomorfizmi grafa;hiperkocke;Cayleyjevi grafi;Sabidussijev izrek;Magma;dekompozicija grafa na cikle;popolno prirejanje;

Data

Language:	Slovenian
Year of publishing:	2019
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[T. Škvarč]
UDC:	519.1
COBISS:	18820953
Views:	1700
Downloads:	309
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Cubic vertex-transitive graphs
Secondary abstract:	The paper's aim is to determinate all cubic vertex-transitive graphs on up to certain order which is given in advance. A graph is $G$-vertex-transitive graph, if subgroup $G$ of graph's group of automorphism acts transitively on its vertex-set. Based on the number of orbits of the vertex-stabiliser $G_v$ in its action on the neighbourhood $\Gamma(v)$ we separate cubic vertex-transitive graphs into three groups. The first group is the group of graphs with only one orbit. Theorem, stating that the action of vertex-stabiliser on the neighbourhood has the same number of orbits as the action of group $G$ on arc-set, connects first group's graphs with cubic arc-transitive ones. The second group is the group of graphs with three orbits. Sabidussi's theorem connets second group's graphs with Cayley's graphs. The last group is the group of graphs with two orbits. Graphs from this group are connected with tetravalent arc-transitive graphs.
Secondary keywords:	mathematics;cubic graphs;vertex-transitive graphs;arc-transitive graphs;group acting on set;stabiliser;orbits;graphs automorphisms;hypercubes;Cayley graphs;Sabidussi theorem;cycle decomposition of graph;perfect matching;
Type (COBISS):	Final seminar paper
Study programme:	0
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Pages:	30 str.
ID:	11228343