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)\}$


[Graph $G$](https://i.stack.imgur.com/lesVr.png)


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\}]$](https://i.stack.imgur.com/ch87i.png)
* remove $v\_0$, reassign to $v\_1$
* reconnect $v\_1$ as [$G[\{v\_1,v\_4,v\_5\}]$](https://i.stack.imgur.com/ZMkhl.png)
* remove $v\_5$ and reassign to $v\_3$
* reconnect $v\_3$ as [$G[\{v\_1,v\_3,v\_5\}]$](https://i.stack.imgur.com/a7YGC.png)
* remove $v\_5$ and reassign to $v\_2$
* reconnect $v\_2$ as [$G[\{v\_1,v\_2,v\_3\}]$](https://i.stack.imgur.com/vAngB.png).


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


1. Place the counters on a subset of vertices $S\subseteq V$
2. A counter may be lifted from a vertex $v$ if and only if each vertex $u\in \mathcal{N}(v)$ also has a counter
3. 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]$
4. 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)\}$


[Graph $G$](https://i.stack.imgur.com/lesVr.png)


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



Connectivity graph invariant
I think what you describe is exactly the "node-search number" as described by Kirousis and Papadimitriou (<https://www.sciencedirect.com/science/article/pii/0012365X85900469>). As shown in that paper, it is indeed equivalent to the interval thickness, or (which is the same) the pathwidth plus one.


