Rigidity and separation indices of Paley graphs

摘要

It is shown that the ratio between separation and rigidity indices of graphs may be arbitrarily large. Paley graphs are such examples.