The Open UniversitySkip to content

Polarity graphs revisited

Bachratý, Martin and Širáň, Jozef (2015). Polarity graphs revisited. Ars Mathematica Contemporanea, 8(1) pp. 55–67.

Google Scholar: Look up in Google Scholar


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].

Item Type: Journal Item
ISSN: 1855-3974
Project Funding Details:
Funded Project NameProject IDFunding Body
Not SetResearch Grants 1/0871/11, 1/0065/13 and 1/0007/14VEGA
Not SetResearch Grants 0223-10 and 0136-12APVV
EUROCORES Programme EUROGIGA, project GREGASESF-EC-0009-10European Science Foundation/APVV
Extra Information: Special Issue in Honor of the 60th Birthday of Professor Dragan Marušič
Keywords: graph; polarity graph; degree; diameter; automorphism; group; vertex-transitive graph; Cayley graph
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 41758
Depositing User: Jozef Širáň
Date Deposited: 20 Jan 2015 14:26
Last Modified: 07 Dec 2018 10:28
Share this page:

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU