Polarity graphs revisited - Bachratý, Martin (Ars mathematica contemporanea, 2015)
Polarnostni grafi, znani tudi kot Brownovi grafi, in njihove manjše modifikacije, so največji trenutno znani grafi premera 2 in dane maksimalne stopnje ?$d$?, kjer je ?$d - 1$? potenca praštevila večja od 5. V luči nedavnega zanimanja za "problem stopenj in premera", omejenega na vozliščno-tranzitivne in Cayleyeve grafe, raziskujemo načine, na katere bi spremenili (ne-regularne) polarnostne grafe v velike vozliščno-tranzitivne grafe premera 2 in dane stopnje. Najprej pregledamo določene lastnosti polarnostnih grafov in predstavimo nove in krajše dokaze. Nato pokažemo, da polarnostni grafi maksimalne sode stopnje ?$d$? ne morejo biti vpeti podgrafi vozliščno-tranzitivnih grafov stopnje največ ?$d + 2$?. Če je ?$d - 1$? potenca števila 2, potem obstajata dva velika vozliščno-tranzitivna inducirana podgrafa ustreznega polarnostnega grafa, eden je stopnje ?$d - 1$?, drugi pa stopnje ?$d - 2$?. Pokažemo, da podgrafov stopnje ?$d - 1$? ni mogoče razširiti do vozliščno-tranzitivnih grafov premera 2 z dodajanjem relativno majhne ne-povezavne orbitale. Dokažemo pa, da je podgrafe stopnje ?d - 2? mogoče razširiti do največjih trenutno znanih Cayleyevih grafov dane stopnje in premera 2, ki sta jih našla Šiagiová in drugi avtor J. Combin. Theory Ser. B 102 (2012), 470-473.
Keywords: automorphism group; Cayley graph; Cayleyjev graf; degree; diameter; graf; graph; grupa avtomorfizmov; polarity graph; polarnostni graf; premer; stopnja; vertex-transitive graph; vozliščno-tranzitiven graf