Polarity graphs revisited
Ars Mathematica Contemporanea, Tome 8 (2015) no. 1, pp. 55-67.
Voir la notice de l'article dans Ars Mathematica Contemporanea website
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].
Mots-clés :
Graph, polarity graph, degree, diameter, automorphism, group, vertex-transitive graph, Cayley graph.
@article{10_26493_1855_3974_527_74e, author = {Martin Bachrat\'y and Jozef \v{S}ir\'a\v{n}}, title = {Polarity graphs revisited}, journal = {Ars Mathematica Contemporanea}, pages = {55--67}, publisher = {mathdoc}, volume = {8}, number = {1}, year = {2015}, doi = {10.26493/1855-3974.527.74e}, language = {en}, url = {https://geodesic-test.mathdoc.fr/articles/10.26493/1855-3974.527.74e/} }
TY - JOUR AU - Martin Bachratý AU - Jozef Širáň TI - Polarity graphs revisited JO - Ars Mathematica Contemporanea PY - 2015 SP - 55 EP - 67 VL - 8 IS - 1 PB - mathdoc UR - https://geodesic-test.mathdoc.fr/articles/10.26493/1855-3974.527.74e/ DO - 10.26493/1855-3974.527.74e LA - en ID - 10_26493_1855_3974_527_74e ER -
Martin Bachratý; Jozef Širáň. Polarity graphs revisited. Ars Mathematica Contemporanea, Tome 8 (2015) no. 1, pp. 55-67. doi : 10.26493/1855-3974.527.74e. https://geodesic-test.mathdoc.fr/articles/10.26493/1855-3974.527.74e/
Cité par Sources :