Polarity graphs revisited - Bachratý, Martin (Ars mathematica contemporanea, 2015)
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-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