Connectivity graph invariant

Question

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$

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

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$

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

Answer 1

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.

Answer 2

This is not a complete answer, but too long for a comment. The punchline is that for very small graphs the statistic seems to coincide with the pathwidth (after subtracting 1), see https://www.findstat.org/StatisticsDatabase/St000536.

More precisely, it seems that the path decomposition provides a sequence of chip placements and vertices to delete as required by the statistic described in the question.

Here is a very naive implementation of the algorithm computing the statistic. Its only purpose is to find the numbers for very small graphs:

def closed_neighbourhood(G, v):
    return G[v] + [v]

def children(G, P):
    r"""We are looking for the minimal number of chips needed such that
    the following process terminates.

    1. place at most one chip on each vertex.
    
    2. if all neighbours of a vertex `v` have a chip, the vertex may
    be removed and the chip may be placed on a different vertex.
    
    3. stop when the graph has no vertices.

    INPUT:

    - G, a graph with vertex set V

    - P, a subset of V

    OUTPUT:

    all pairs `(H, C)` of graphs `H` and chip placements `C` that can
    be obtained from `(G, P)` by removing a single (removable) vertex.
    """
    for v in G.vertices(sort=False):
        N = closed_neighbourhood(G, v)
        if all(u in P for u in N):
            H = G.copy(immutable=False)
            H.delete_vertex(v)
            Q = P.difference([v])
            U = set(H.vertices(sort=False)).difference(Q)
            if not U:
                yield (H.copy(immutable=True), Q)
            else:
                for u in list(U):
                    yield (H.copy(immutable=True), Q.union([u]))

def statistic_aux(G, k):
    G = G.canonical_label().copy(immutable=True)
    V = G.vertices(sort=False)
    R = RecursivelyEnumeratedSet([(G, frozenset(P)) for P in Subsets(V, k)],
                                 lambda x: children(x[0], x[1]))
    return R

@cached_function
def statistic(G):
    """
    sage: [statistic(graphs.PathGraph(n)) for n in range(2,7)]
    [2, 2, 2, 2, 2]
    sage: [statistic(graphs.CycleGraph(n)) for n in range(3,7)]
    [3, 3, 3, 3]
    sage: [statistic(graphs.CompleteGraph(n)) for n in range(1,7)]
    [1, 2, 3, 4, 5, 6]
    sage: [statistic(graphs.StarGraph(n)) for n in range(4,7)]
    [2, 2, 2]
    sage: [[statistic(graphs.CompleteBipartiteGraph(m, n)) for m in range(2, n+1)] for n in range(3,7)]
    [[3, 4], [3, 4, 5], [3, 4, 5, 6], [3, 4, 5, 6, 7]]
    """
    for k in range(G.num_verts()+1):
        R = statistic_aux(G, k)
        if any(H.num_verts() == 0 for H, P in R):
            return k

Plugging the first 1000 statistic values, corresponding to graphs on at most 6 vertices (and most graphs with 7 vertices) into findstat, we obtain:

sage: qu = findstat("graphs", statistic, depth=0); qu
0: St000536 with offset -1 (quality [100, 100])
sage: qu[0].info()
after subtracting 1 from every value

your input matches
    St000536: The pathwidth of a graph.

among the values you sent, 100 percent are actually in the database,
among the distinct values you sent, 100 percent are actually in the database

So, the next step is to find a graph whose pathwidth is different from this statistic, or prove that this statistic is actually the pathwidth (after subtracting 1), or find a bug in the program.

In fact, the coincidence holds for all graphs on at most 8 vertices:

sage: n=8; all(G.pathwidth() == statistic(G.canonical_label().copy(immutable=True))-1 for G in graphs(n))
True

Finally, here is a program that checks that a path decomposition has the required properties:

def check_decomposition(H, verbose=False):
    G = H.copy(immutable=False)
    k, D = G.pathwidth(certificate=True)
    V = D.vertices(sort=False)
    if verbose: print(V)
    for i in range(len(V)):
        if i < len(V)-1:
            lv = V[i].difference(V[i+1])
        else:
            lv = V[i]
        if verbose: print("removing %s" % lv)
        for v in lv:
            assert set(V[i]).issuperset(G[v]), "not all neighbours have a chip"
            G.delete_vertex(v)
    return not G.num_verts()