Geodesic
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].
DOI : 10.26493/1855-3974.527.74e
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  - 
%0 Journal Article
%A Martin Bachratý
%A Jozef Širáň
%T Polarity graphs revisited
%J Ars Mathematica Contemporanea
%D 2015
%P 55-67
%V 8
%N 1
%I mathdoc
%U https://geodesic-test.mathdoc.fr/articles/10.26493/1855-3974.527.74e/
%R 10.26493/1855-3974.527.74e
%G en
%F 10_26493_1855_3974_527_74e
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 :