Home > News > Primož Šparl: Tranzitivno delovanje grup na grafih

Primož Šparl: Tranzitivno delovanje grup na grafih

Date: 5. 11. 2007
Source: Discrete mathematics seminar
Torek, 6.11.2007 od 10:15 do 12:00, Plemljev seminar, Jadranska 19/III, Ljubljana

Povzetek:
Predstavil bom rezultate, ki jih zajema moja doktorska disertacija z enakim naslovom. Glavna tema le-te so grafi, ki dopuščajo  poltranzitivno podgrupo avtomorfizmov, to je podgrupo, ki deluje tranzitivno na množici točk in množici povezav, ne pa tudi na množici urejenih parov sosednih točk tega grafa. Graf je poltranzitiven, če njegova  grupa avtomorfizmov deluje poltranzitivno. Trenutno ne znamo klasificirati niti poltranzitivnih grafov najmanjše možne stopnje, to je stopnje štiri. Rezultati te disertacije nas pripeljejo korak bliže k temu cilju.

Prvi del,  je posvečen klasifikaciji tako imenovanih tesno spetih poltranzitivnih grafov stopnje 4. Vsakemu štirivalentnemu poltranzitivnemu grafu X pripada množica tako imenovanih izmeničnih ciklov, ki so vsi iste sode dolžine. Polovico te dolžine imenujemo radij grafa X. Poleg tega imata poljubna nedisjunktna izmenična cikla grafa X isto število skupnih točk. Če je to število, ki ga imenujemo spojno število grafa X,
enako radiju grafa X, pravimo, da je graf X tesno spet. V  J.Comb.Theory Ser. B {73} (1998) 41--76, je Marušič klasificiral štirivalentne tesno spete poltranzitivne grafe lihega radija. V tem delu klasificiramo grafe sodega radija, s čimer zaključimo klasifikacijo  štirivalentnih tesno spetih poltranzitivnih grafov.

V drugem delu se ukvarjamo s štirivalentnimi poltranzitivnimi šibkimi metacirkulanti. Graf je šibek metacirkulant, če dopušča tranzitivno grupo avtomorfizmov, generirano z dvema avtomorfizmoma $\rho$ in $\sigma$, kjer je avtomorfizem $\rho$ polregularen, avtomorfizem $\sigma$ pa normalizira $\rho$ ter ciklično vrti njegove orbite. Najprej pokažemo, da vsak štirivalenten poltranzitiven šibek metacirkulant pripada vsaj enemu izmed štirih razredov takih grafov. Nato pokažemo, da eden izmed teh razredov sovpada z družino štirivalentnih tesno spetih poltranzitivnih grafov. Posvetimo se še enemu izmed omenjenih štirih razredov. Analiziramo kdaj tak graf ni tesno spet, konstruiramo neskončno družino grafov tega razreda, ki niso tesno speti, ta razred pa tudi klasificiramo.