<p>Vertex-minors of complete graphs are either complete graphs, star graphs, or edgeless graphs, so this does not hold for <span class="math-container">$k \ge 2$</span>.</p>
<p>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.</p>

CC BY-SA 4.0
2021-12-29T13:15:54.283Z
local completion of a complete graph is edge less graph not star.
Saeed
CC BY-SA 4.0
2021-12-29T15:58:45.827Z
@Saeed I think it is a star, using the definition given in the paper "Rank-width and vertex-minors" by Oum '05.
Laakeri
CC BY-SA 4.0
2021-12-31T16:09:44.330Z
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.
Saeed
CC BY-SA 4.0
2021-12-29T11:14:44.900Z
2021-12-29T11:14:44.900Z
Laakeri
<p>Consider a graph <span class="math-container">$G$</span>. A graph <span class="math-container">$H$</span> is the vertex-minor of the graph <span class="math-container">$G$</span> if <span class="math-container">$H$</span> can be obtained from <span class="math-container">$G$</span> using vertex deletions and local complementations. For more information, look at Definition 2.1 and 2.2 <a href="https://arxiv.org/pdf/1906.05689.pdf" rel="nofollow noreferrer">here</a>.</p>
<p>Now, let <span class="math-container">$G$</span> be a complete graph with <span class="math-container">$n^{2}$</span> vertices and let <span class="math-container">$H$</span> be a <span class="math-container">$k \times k$</span> grid graph, with <span class="math-container">$k &lt; n$</span>.</p>
<p>For some choice of <span class="math-container">$k$</span>, is <span class="math-container">$H$</span> a vertex-minor of <span class="math-container">$G$</span>?</p>

CC BY-SA 4.0
2021-12-29T03:40:18.943Z
How is it clear from the definition?
AngryLion
CC BY-SA 4.0
2021-12-29T13:18:15.283Z
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.
Saeed
CC BY-SA 4.0
2022-01-24T22:46:14.527Z
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, https://cstheory.stackexchange.com/help/on-topic. Your question might be suitable for Computer Science which has a broader scope, https://cs.stackexchange.com/.
Neal Young
<ds.algorithms><graph-theory><graph-algorithms><planar-graphs>
Is a grid graph a vertex-minor of a complete graph?
AngryLion
# Is a grid graph a vertex-minor of a complete graph?

(Asked by: username_0 on 2021-12-28)

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](https://arxiv.org/pdf/1906.05689.pdf).

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, planar-graphs
> **Comments:**
> **username_0**: How is it clear from the definition?  
> **username_1**: 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.  
> **username_2**: 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, https://cstheory.stackexchange.com/help/on-topic. Your question might be suitable for Computer Science which has a broader scope, https://cs.stackexchange.com/.  

---

## 1 answers

### Answer by username_3 on 2021-12-29. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_1**: local completion of a complete graph is edge less graph not star.  
> **username_3**: @Saeed I think it is a star, using the definition given in the paper "Rank-width and vertex-minors" by Oum '05.  
> **username_1**: 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.  

---

