20.500.12556/RUL-110747 3-valentni vozliščno tranzitivni grafi delo diplomskega seminarja Cubic vertex-transitive graphs 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. 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. kubični grafi vozliščno tranzitivni grafi ločno tranzitivni grafi delovanje grupe na množico stabilizator orbita avtomorfizmi grafa hiperkocke Cayleyjevi grafi Sabidussijev izrek Magma dekompozicija grafa na cikle popolno prirejanje. cubic graphs vertex-transitive graphs arc-transitive graphs group acting on set stabiliser orbit graphs automorphisms hypercubes Cayley's graphs Sabidussi's theorem Magma cycle decomposition of graph perfect matching. true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2019-09-19 07:45:46 2019-09-19 07:45:48 2024-05-30 10:22:01 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.1 99892 18820953 1080.pdf 1080.pdf 1 89175437CD6B6D04B97E49DA83B3E5EE 7aed3e081bcf7c485efd7dc9864e303b1742c619ff329cb0a2b1f3fff22707f8 324a46e5-a1b7-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=122448 Fakulteta za matematiko in fiziko 0 0 0