5
$\begingroup$

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:

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

$\endgroup$
6
  • $\begingroup$ I admit that I do not understand the description ("once a vertex, $v$, has been connected to all vertices $u\in\mathcal N(v)$" - but by definition, $v$ is connected to all its neighbours). However, one way to check whether the statistic might be known is to enter the first few values into findstat.org/StatisticFinder/?Domain=Cc0020, or, in case you have sagemath code that produces the values, use the interface to findstat. $\endgroup$ Commented Aug 17, 2023 at 14:24
  • $\begingroup$ findstat.org/permalink/ef8dd5fbd943999def0819c3f5a60ab9 $\endgroup$ Commented Aug 17, 2023 at 14:25
  • $\begingroup$ Two questions: (1) it seems to me, that "counter" is misleading, since they are just binary, or am I missing something? If they are just binary, it might be better to say that the vertices are marked. (2) isn't "or have a counter" redundant? If all vertices have a counter, I can remove any vertex, and this will not change the state of the other vertices. If true, it would be less confusing if the last step is "4. Repeat until all vertices have been removed." $\endgroup$ Commented Aug 18, 2023 at 7:25
  • $\begingroup$ A third question: can't we simply combine steps 2. and 3. by saying: "a vertex may be removed if all its neighbours have a counter" (or, if you follow my suggestion: "are marked"). $\endgroup$ Commented Aug 18, 2023 at 7:27
  • $\begingroup$ Oh, and from the worked example, I see why you use the "lift" and "place" terminology. So, would the following description be correct? 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. $\endgroup$ Commented Aug 18, 2023 at 7:32

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks! After Martin's answer, we also found this paper which references the pebble game! $\endgroup$ Commented Aug 22, 2023 at 0:45
5
$\begingroup$

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()
$\endgroup$
1
  • $\begingroup$ This is very helpful! We'll have a go at confirming this. Thank you very much. $\endgroup$ Commented Aug 19, 2023 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.