Calum Buchanan, University of Vermont

Abstract

It is possible to obtain any simple graph G from any other graph H on the same set of vertices V by performing a sequence of subgraph complementations. That is, we can iteratively replace induced subgraphs by their graph complements until we obtain G from H. We ask for the minimum number of subgraph complementations in such a sequence, which can be reduced to finding the minimum number of subgraph complementations needed to obtain G from the graph on V with no edges. Finding this number, which we denote by c2(G), relates closely to the minimum rank problem. We show that c2(G) = mr(G, F2) when mr(G, F2) is odd or when G is a forest; otherwise, mr(G, F2) ≤ c2(G) ≤ mr(G, F2) + 1. We then provide two conditions equivalent to having c2(G) = mr(G, F2) + 1 and give a combinatorial interpretation of mr(G, F2) in this case as well. Finally, the class of graphs G with c2(G) ≤ k is hereditary and finitely defined, and we exhibit the sets of minimal forbidden induced subgraphs for small values of k. 

This is joint work with Christopher Purcell and Puck Rombach.

See: https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html