I am interested in the following graph invariant: for a given graph $G=(V,E)$, $c(G)$ is defined to be the smallest number of vertices such that I can recreate the connectivity of $G$ by disconnecting and relabelling vertices for reuse once they have been connected to all vertices in their neighborhood in $G$. That is, once a vertex, $v$, has been connected to all vertices $u \in \mathcal{N}(v)$, all edges incident to $v$ can be removed so that the vertex $v$ can be relabeled and used to recreate connectivity elsewhere. Note that we allow vertices $u\in\mathcal{N}(v)$ to have already been disconnected and relabelled prior to disconnecting and relabelling $v$, so long as they have been connected previously.

Some simple observations include:

- For a clique $K_n$, $c(K_n)=n$.
- For any path graph $P_\ell$, $c(P_\ell)=2$
- For any cycle $C_m$ with $m>2$ $c(C_m)=3$.
- For a star graph $K_{1,n}$ $c(K_{1,n})=2$
- For a complete bipartite graph $K_{m,n}$ $c(K_{m,n})=\min(m,n)+1$
- The number is lower bounded by the order of the largest clique $K\subset G$

I would be interested to know if this graph invariant has been studied before.

This problem seems to be related to graph bubbling in the sense that we wish to reduce the number of vertices present by cutting across the minimal number of edges.

## Worked Example

Consider the graph $G=(V,E)$ with $V=\{v_i\}_{i=0}^5$ and edge set $E=\{(v_0,v_4), (v_1,v_2), (v_1,v_3), (v_1,v_4), (v_2,v_3), (v_3,v_5),(v_4,v_5)\}$

The connectivity of this graph can be recreated using a minimum of three vertices. To do so, we create the following induced subgraphs in turn:

- create $G[\{v_0,v_4,v_5\}]$
- remove $v_0$, reassign to $v_1$
- reconnect $v_1$ as $G[\{v_1,v_4,v_5\}]$
- remove $v_5$ and reassign to $v_3$
- reconnect $v_3$ as $G[\{v_1,v_3,v_5\}]$
- remove $v_5$ and reassign to $v_2$
- reconnect $v_2$ as $G[\{v_1,v_2,v_3\}]$.

# Alternative definition

for a given graph $G=(V,E)$, $c(G)$ is defined to be the smallest number of counters that we can use to cover all vertices in $V$, with following prescription

- Place the counters on a subset of vertices $S\subseteq V$
- A counter may be lifted from a vertex $v$ if and only if each vertex $u\in \mathcal{N}(v)$ also has a counter
- When a counter is lifted we update the graph by removing the vertex from which the counter was lifted: $G\gets G[V\setminus v]$
- Repeat until all vertices have been removed or have a counter

## Worked Example

Consider the graph $G=(V,E)$ with $V=\{v_i\}_{i=0}^5$ and edge set $E=\{(v_0,v_4), (v_1,v_2), (v_1,v_3), (v_1,v_4), (v_2,v_3), (v_3,v_5),(v_4,v_5)\}$

We have $c(G)=3$ using the following method

- place counters on vertices $\{v_0,v_4,v_5\}]$
- lift counter from $v_0$
- Set $G\gets G[V\setminus v_0]$
- Place counter on $v_1$
- lift counter from $v_5$
- Set $G\gets G[V\setminus v_5]$
- place counter on $v_3$
- lift counter from $v_3$
- Set $G\gets G[V\setminus v_3]$
- place counter on $v_2$

Now all vertices have either been removed or have a counter

1more comment