@Article{RV76b,
author = { Ronald L. Rivest and Jean Vuillemin },
title = { On recognizing graph properties from adjacency matrices },
journal = { Theoretical Computer Science },
OPTyear = { 1976 },
OPTmonth = { December },
date = { 1976-12 },
pages = { 371--384 },
volume = { 3 },
number = { 3 },
publisher = { North-Holland },
doi = { 10.1016/0304-3975(76)90053-0 },
abstract = {
A conjecture of Aanderaa and Rosenberg [5] motivates this work.
We investigate the maximum number $C(P)$ of arguments of $P$ that
must be tested in order to compute $P$, a Boolean function of $d$
Boolean arguments. We present evidence for the general conjecture
that $C(P)=d$ whenver $P(0^d)\ne P(1^d)$ and $P$ is invariant under
a transitive permutation group acting on the arguments. A
non-constructive argument (not based on the construction of an
``oracle'') settles this question for $d$ a prime power. We use
this result to prove the Aanderaa-Rosenberg conjecture: at least
$v^2/16$ entries of the adjacency matrix of a $v$-vertex undirected
graph $G$ must be examined in the worst case to determine if $G$ has
any given non-trivial monotone graph property.
},
}