Unexpected symmetries in unstable graphs

Steve Wilson

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


This paper considers instability of graphs in all of its possible forms. First, four theorems (one with two interesting special cases) are presented, each of which shows that graphs satisfying certain conditions are unstable. Several infinite families of graphs are investigated. For each family, the four general theorems are used to find and prove enough theorems particular for the family to explain the instability of all graphs in the family up to a certain point. A very dense family of edge-transitive unstable graphs is constructed and, at the other extreme, an unstable graph is constructed whose only symmetry is trivial. Finally, the four theorems are shown to be able to explain all instability.

Original languageEnglish (US)
Pages (from-to)359-383
Number of pages25
JournalJournal of Combinatorial Theory. Series B
Issue number2
StatePublished - Mar 2008


  • Anti-symmetry
  • Automorphism group
  • Cross-cover
  • Graph
  • Symmetry
  • Unstable graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Unexpected symmetries in unstable graphs'. Together they form a unique fingerprint.

Cite this