Graph Labelings Obtainable by Random Walks

2023/04/12 by Sela Fried, Fried, Sela, Toufik Mansour +1
Mathematics · Computer Science · #Graph theory and applications #Advanced Combinatorial Mathematics #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2304.05728

Abstract

We initiate the study of what we refer to as random walk labelings of graphs. These are graph labelings that are obtainable by performing a random walk on the graph, such that the labeling occurs increasingly whenever an unlabeled vertex is encountered. Some of the results we obtain involve sums of inverses of binomial coefficients, for which we obtain new identities. In particular, we prove that ∑_k=0^n-12^k(2k+1)^-1\binom2kk^-1\binomn+kk=\binom2nn2^-n∑_k=0^n-12^k(2k+1)^-1\binom2kk^-1, thus confirming a conjecture of Bala.

Related

• Further Results on Random Walk Labelings
• Random Walk Labelings of Perfect Trees and Other Graphs
• Label propagation on binomial random graphs
• Canonization of a random graph by two matrix-vector multiplications
• On The Number Of Labeled Bipartite Graphs