# Is a grid graph a vertex-minor of a complete graph? [closed]

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$$?

• How is it clear from the definition? Dec 29, 2021 at 3:40
• You could simply put the definition of local completion here (even though it is natural, but not common), that's the least you should do to make your question self-contained. Additionally, the answer to this question is trivial by definition, certainly not a research-level question. Dec 29, 2021 at 13:18
• Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center, cstheory.stackexchange.com/help/on-topic. Your question might be suitable for Computer Science which has a broader scope, cs.stackexchange.com. Jan 24 at 22:46

Vertex-minors of complete graphs are either complete graphs, star graphs, or edgeless graphs, so this does not hold for $$k \ge 2$$.
• I'm saying this based on the definition of the linked paper of the OP, it says: "replacing the induced subgraph on the neighborhood of v, i.e. $G[N_v]$, by its complement". Since the neighborhood of any vertex is the entire graph, its complement is an empty graph. If they mean open neighborhood, they shouldn't use that notation, but I think they mean closed neighborhood anyways (the more natural one that is compatible with their notation). Also if your answer is based on a different definition, then include the other definition here. Dec 31, 2021 at 16:09