Abstract. This article studies labeling schemes for the vertex connectivity function on general graphs. We consider the problem of assigning short labels to the nodes of any n-node graph is such a way that given the labels of any two nodes u and v, one can decide whether u and v are k-vertex connected in G, that is, whether there exist k vertex disjoint paths connecting u and v. This article establishes an upper bound of k 2 log n on the number of bits used in a label. The best previous upper bound for the label size of such a labeling scheme is 2 k log n.
The vertex-connectivity labeling scheme described in REF is the most related to our context.
Labeling schemes for vertex connectivity
TALG
Mathematics Computer Science