IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

A Characterization of Uniquely Pressable Simple Pseudo-Graphs

  • March 24, 2017
  • 2:30 p.m.
  • LeConte 312

Abstract

The pressing game on simple pseudo-graphs (graphs that allow loops but not multiple edges) is the following: given a simple pseudo-graph $G=(V,E)$ any looped vertex $v$ can be pressed to create a new graph $G'$, a new simple pseudo-graph in which $G[N(v)]$ is complemented. That is, $V(G')=V(G)$ and $E(G')=E(G)\triangle\{N(v)\times N(v)\}$. The aim of the game is to transform $G$ into an edgeless (loopless) simple pseudo-graph. The ordered set of vertices pressed to achieve the transformation is referred to as a successful pressing sequence. It is known that successful pressing sequences exist iff the simple pseudo-graph contains at least one looped vertex in each non-trivial component. In a recent paper Joshua Cooper and Jeffrey Davis discussed the existence of a set of simple pseudo-graphs that allow exactly one successful pressing sequence: the set of uniquely pressable graphs. In this talk we give a complete characterization of this set.

The pressing game has connections to genome rearrangement and sorting signed permutations by reversal. This is joint work with Joshua Cooper.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC