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

  • $\begingroup$ How is it clear from the definition? $\endgroup$
    – AngryLion
    Dec 29, 2021 at 3:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Dec 29, 2021 at 13:18
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Jan 24, 2022 at 22:46

1 Answer 1


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.

  • $\begingroup$ local completion of a complete graph is edge less graph not star. $\endgroup$
    – Saeed
    Dec 29, 2021 at 13:15
  • $\begingroup$ @Saeed I think it is a star, using the definition given in the paper "Rank-width and vertex-minors" by Oum '05. $\endgroup$
    – Laakeri
    Dec 29, 2021 at 15:58
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Dec 31, 2021 at 16:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.