302 KB40 KB200820252015Bachratý, MartinŠiran, Jozefštevilka:1letnik:8str. 55-67COBISSID:17368409ISSN:1855-3966URN:URN:NBN:SI:doc-42YOT5WGenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaautomorphism groupCayley graphCayleyjev grafdegreediametergrafgraphgrupa avtomorfizmovpolarity graphpolarnostni grafpremerstopnjavertex-transitive graphvozliščno-tranzitiven grafPolarity graphs revisited|Polarity graphs, also known as Brown graphs, and their minor modifications are the largest currently known graphs of diameter 2 and a given maximum degree ?$d$? such that ?$d - 1$? is a prime power larger than 5. In view of the recent interest in the degree-diameter problem restricted to vertex-transitive and Cayley graphs we investigate ways of turning the (non-regular) polarity graphs to large vertex-transitive graphs of diameter 2 and given degree. We review certain properties of polarity graphs, giving new and shorter proofs. Then we show that polarity graphs of maximum even degree ?$d$? cannot be spanning subgraphs of vertex-transitive graphs of degree at most ?$d + 2$?. If ?$d - 1$? is a power of 2, there are two large vertex-transitive induced subgraphs of the corresponding polarity graph, one of degree ?$d - 1$? and the other of degree ?$d - 2$?. We show that the subgraphs of degree ?$d - 1$? cannot be extended to vertex-transitive graphs of diameter 2 by adding a relatively small non-edge orbital. On the positive side, we prove that the subgraphs of degree ?$d - 2$? can be extended to the largest currently known Cayley graphs of given degree and diameter 2 found by Šiagiová and the second author J. Combin. Theory Ser. B 102 (2012), 470-473Polarnostni 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-473TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije