Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Consider a graph $G$. A graph $H$ is the vertex-minor of the graph $G$ if $H$ can be obtained from $G$ using vertex deletions and local complementations. For more information, look at Definition 2.1 and 2.2 here.
Now, let $G$ be a complete graph with $n^{2}$ vertices and let $H$ be a $k \times k$ grid graph, with $k < n$.
For some choice of $k$, is $H$ a vertex-minor of $G$?
Vertex-minors of complete graphs are either complete graphs, star graphs, or edgeless graphs, so this does not hold for $k \ge 2$.
Proof that vertex-minors of complete graphs are complete, star, or edgeless: From a complete graph, vertex deletion gives a complete graph and local complementation gives a star graph. From a star graph, deletion of the central vertex gives an edgeless graph, local complementation of the central vertex gives a complete graph, deletion of an outer vertex gives a star graph, and local complementation of an outer vertex gives again the same star graph. From an edgeless graph, both vertex deletion and local complementation give again an edgeless graph.
