Premium
The evasiveness conjecture and graphs on 2 p vertices
Author(s) -
Ángel Andrés,
Borja Jerson
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22419
Subject(s) - combinatorics , mathematics , conjecture , chordal graph , discrete mathematics , vertex (graph theory) , monotone polygon , counterexample , graph , geometry
The evasiveness conjecture has been proved for properties of graphs on a prime‐power number of vertices and the six‐vertex case. The 10‐vertex case is still unsolved. In this paper we study the size of the automorphism group of a graph on 2 p vertices to estimate the Euler characteristic of monotone nonevasive graph properties. We get some conditions on graphs that such graph properties must contain. We also do this by means of Oliver groups and give a new lower bound for the dimension of the simplicial complex associated with a nontrivial monotone nonevasive graph property. We apply our results to graphs on 10 vertices to get conditions on potential counterexamples to the evasiveness conjecture in the 10‐vertex case.