Preizkusite novo različico: COBISS+
 Lokalna baza podatkov: FMF in IMFM, Matematična knjižnica, Ljubljana (Štev. zapisov: 63.575) | Domača stran knjižnice

Izbrani zapis trajna povezava

AvtorEstélyi, István
Naslov Haar graphs : doctoral thesis / István Estélyi
Drugi nasloviHaarovi grafi
Vrsta/vsebinatype of material disertacija
Jezikangleški
Leto2016
Založništvo in izdelavaLjubljana : [I. Estélyi], 2016
Ostali avtorjiPisanski, Tomaž
Kovács, István, 1969-
Fizični opis81 str. : ilustr. ; 30 cm
OpombeNasl. str. tudi v slov.: Haarovi grafi
Mentor Tomaž Pisanski, somentor István Kovács
Bibliografija: str. 63-67
Abstract ; Povzetek ; Razširjeni slov. povzetek
Univ. Ljubljana, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 3. stopnja
Predmetne oznake (nekontrolirane)matematika / Cayleyevi grafi / Haarovi grafi / bi-Cayleyjevi grafi / celoštevilski grafi / celoštevilska Cayleyeva grupa / mathematics / Cayley graphs / Haar graphs / bi-Cayley graphs / integral graphs / Cayley integral group
UDK519.17(043.3)
Druge klasifikacije
20B25
05C25
05C50
20C10
05E10 (MSC 2010)
PovzetekV tej doktorski disertaciji obravnavamo dve področji algebrajske teorije grafov. Do vključno 4. poglavja preučujemo zvezo med Cayleyjevimi, Haarovimi, bi-Cayleyjevimi in vozliščno tranzitivnimi grafi. Vsi našteti so tesno povezani s Cayleyjevimi grafi. Slednji imajo grupo avtomorfizmov, ki deluje regularno na množici vozlišč. Haarovi grafi, ki so jih uvedli Hladnik, Marušič in Pisanski, so dvodelni grafi in imajo semiregularno grupo avtomorfizmov, ki deluje regularno na vsakem delu dvodelnega razbitja. Haarovi grafi tvorijo poseben podrazred bi-Cayleyjevih grafov. Slednji imajo semiregularno grupo avtomorfizmov z dvema orbitama, ki nista nujno neodvisni množici. V 3. poglavju se lotimo problema klasifikacije končnih nekomutativnih grup $G$ z lastnostjo, da je vsak Haarov graf nad $G$ tudi Cayleyjev graf. Podamo ekvivalenten pogoj, ki mora veljati za $G$, podmnožico $S$ in $\text{Aut} G$, da bo Haarov graf nad $G$ tudi Cayleyjev graf neke grupe, ki vsebuje $G$. Zgornji problem smo do potankosti rešili za diedrske grupe. Pokazali smo, da so $\mathbb{Z}_2^2$, $D_3$, $D_4$ in $D_5$ vse diedrske grupe, po katerih povprašujemo zgoraj. Nedavno sta Estelyi in Pisanski zastavila vprašanje, če obstajajo vozliščno tranzitivni Haarovi grafi, ki niso Cayleyjevi. V 4. poglavju konstruiramo neskončno družino kubičnih Haarovih grafov, ki so vozliščno tranzitivni, toda niso Cayleyjevi. Najmanjši primerek takega grafa ima 40 vozlišč in je dobro znani Kroneckerjev krov nad grafom dodekaedra $P(10, 2)$ ter nosi številko '40' v Fosterjevem cenzusu povezanih simetričnih kubičnih grafov. V drugem delu (5. in 6. poglavje) preučujemo naslednjo lastnost grup. Končni grupi $G$ pravimo celoštevilska Cayleyjeva grupa, če so vsi Cayleyjevi grafi nad $G$ celoštevilski, tj. če so vse lastne vrednosti grafa cela števila. Vse takšne abelove grupe sta našla Kloster in Sander, vse nekomutativne pa Abdollahi in Jazaeri ter neodvisno od njiju se Ahmady, Bell in Mohar. Ta razred grup lahko posplošimo tako, da uvedemo razred $\mathcal{G}_k$ ki vsebuje vse tiste končne grupe $G$, za katere so grafi $\text{Cay} (G, S)$ celoštevilski, takoj ko je $|S| \le k$. Dokazali smo, da $\mathcal{G}_k$ vsebuje natanko celoštevilske Cayleyjeve grupe, če je $k \ge 6$, in da sta razreda $\mathcal{G}_4$ in $\mathcal{G}_5$ enaka in vsebujeta: (1) celoštevilske Cayleyjeve grupe in (2) posplošene diciklične grupe $\rm{Dic}(\mathbb{Z}_3^n \times \mathbb{Z}_6)$, kjer je $n \ge 1$.
In this PhD thesis two topics in algebraic graph theory are investigated. Up to chapter 4 we study the relationship between Cayley graphs, Haar graphs, bi-Cayley graphs and vertex-transitive graphs. All these are closely related to Cayley graphs, which admit a group of automorphisms that act regularly on the set of vertices. The Haar graphs, introduced by Hladnik, Marušič and Pisanski, are bipartite graphs admitting a semiregular group of automorphisms acting regularly on each part. Haar graphs form a subclass of bi-Cayley graphs, where the two orbits do not need to be independent sets. In chapter 3 we address the problem of classifying finite non-abelian groups $G$ with the property that every Haar graph over $G$ is a Cayley graph. An equivalent condition for a Haar graph over $G$ to be a Cayley graph of a group containing $G$ is derived in terms of $G$, the connection set $S$ and $\text{Aut} G$. It is also shown that the dihedral groups, which are solutions to the above problem, are $\mathbb{Z}_2^2$, $D_3$, $D_4$ and $D_5$. Recently Estelyi and Pisanski raised a question whether there exist vertex-transitive Haar graphs that are not Cayley graphs. In Chapter 4 we construct an infinite family of trivalent Haar graphs that are vertex-transitive but non-Cayley. The smallest example has 40 vertices and is the well-known Kronecker cover over the dodecahedron graph $P(10, 2)$, occurring as the graph '40' in the Foster census of connected symmetric trivalent graphs. In chapters 5-6 the following group property is investigated. A finite group $G$ is called Cayley integral if all Cayley graphs over $G$ are integral, i.e., all eigenvalues of the graphs are integers. The Cayley integral groups have been determined by Kloster and Sander in the abelian case, and by Abdollahi and Jazaeri, and independently by Ahmady, Bell and Mohar in the non-abelian case. We generalize this class of groups by introducing the class gk of finite groups $G$ for which all graphs $\text{Cay} (G, S)$ are integral if $|S| \le k$. It will be proved that gk consists of the Cayley integral groups if $k \ge 6$; and the classes $\mathcal{G}_4$ and $\mathcal{G}_5$ are equal, and consist of: (1) the Cayley integral groups, (2) the generalized dicyclic groups $\rm{Dic}(\mathbb{Z}_3^n \times \mathbb{Z}_6)$, where $n \ge 1$.
COBISS.SI-ID18019417

Statusi v izposoji

Podatki o izvodu (signatura - lokacija, inventarna št. ...) Status izvoda Rezervacija
Knjižnica 14521/27 001availability  prosto - za čitalnico