The regular seminar time is Wednesday, 3:35 - 4:25 p.m. The seminar takes place in person in Stevenson Center 1432. The seminar coordinator this semester is Anna Yu, anna.c.yu at vanderbilt.edu . Some seminars may be at unusual times, or may be given as Zoom talks.
Vertex-switching reconstruction – Mark Ellingham (Vanderbilt University)
The vertex-switching reconstruction problem (VSRP) was introduced by Richard Stanley in 1985. A switching at a vertex v in a simple graph G removes all edges from v to N(v) and replaces them by edges from v to V(G)-N(v)-{v}, forming a graph Gv. The vertex-switching deck of G is the collection (multiset) of isomorphism classes of the graphs Gv for all v in V(G). A graph is vertex-switching reconstructible if this deck determines G up to isomorphism. Stanley showed that every n-vertex graph is vertex-switching reconstructible provided n is not divisible by 4. There are graphs on 4 vertices that are not vertex-switching reconstructible, but the question remains open for larger graphs with order divisible by 4. In 1992 Royle and the speaker showed that triangle-free graphs are vertex-switching reconstructible. In this talk we discuss these results and the algebraic techniques used to prove them, in the hope of generating new interest in the VSRP.
Mark Ellingham / mark.ellingham at vanderbilt.edu