Vertex minors of paths

122 Views Asked by At

(Vertex Minor) A graph H is a vertex minor of G if H can be obtained from G by a sequence of vertex deletions and local complementation

(Local complementation) A local complementation $\tau_v$ is a graph operation specified by a vertex $v$, taking a graph $G$ to $\tau_v(G)$ by replacing the induced subgraph on the neighborhood of $v$, i.e. $G\left[N_v\right]$, by its complement. The neighborhood of any vertex $u$ in the graph $\tau_v(G)$ is therefore given by $$ N_u^{\left(\tau_v(G)\right)}= \begin{cases}N_u \Delta\left(N_v \backslash\{u\}\right) & \text { if }(u, v) \in E(G), \\ N_u & \text { otherwise.}\end{cases} $$

The question

What is the minimum $m$ such that $K_n$( complete graph with $n$ vertices) is a vertex-minor of the path graph $P_m$ on $m$ vertices?

My attempt

The best I've got so far is $m=2n-3$.

Here's an example. The path graph with $m=2n-3=7$

Perform the operations $LC[i+1]\,D[i]\,LC[i]\,LC[i+1]$ in sequence; where $i\in{3,5}$ ,$LC[i]$ is local complementation on vertex $i$, $D[i]$ is deletion of vertex $i$. Then we get,

enter image description here

The complete graph with $n=5$

The operations $LC[i+1]\,D[i]\,LC[i]\,LC[i+1]$ are of special relevance in my field, it corresponds to a certain kind of measurement on a physical system. Thus my protocol is just a set of measurements of the systems corresponding to odd vertices. I was thus hoping that $m=2n-3$ is the minimum since I could then show the optimality of my protocol.

Even if not a proof, I would like to know existing research in this direction.