Details of talk

TitleThe switching-stable graphs
PresenterJeanette McLeod (University of Canterbury)
Author(s)Jeanette McLeod, Brendan McKay
SessionAlgebra and Discrete Mathematics
Time14:30:00 2017-09-25
Abstract


  The classical reconstruction problem asks when a graph $G$ can be
reconstructed from its \emph{deck}, where the deck consists of \emph{cards}
showing each of the vertex-deleted subgraphs of~$G$. Stanley, Bondy and others
introduced variants of this problem, where the cards instead show the graphs
obtained by \emph{switching}~$G$. While investigating switching reconstruction
problems, Bondy asked which graphs have the property that every possible
switching produces a graph that is equivalent to the original graph. Such graphs
are said to be \emph{switching-stable}.
  
We answer Bondy's question for two types of switching. First, we let the edges
of $G$ be coloured with two colours and define the switching operation to be the
interchange of the colours of the edges incident to a specified vertex and
classify all switching-stable 2-edge-coloured graphs. Then, we let $G$ be a
digraph and define the switching operation to be the reversal of the directions
of the edges incident to a specified vertex and classify all switching-stable
digraphs. For both variants of switching, we consider the problem for two
different types of equivalence.

Back To Timetable