Exponential Independence in Subcubic Graphs

Speaker: Stéphane Bessy (LIRMM)

Abstract: A set S of vertices of a graph G is exponentially independent if, for every vertex u in S, sum for v in S minus u of (1/2)^{ dist_(G,S) (u,v)−1} is smaller than 1, where dist_(G,S) (u, v) is the distance between u and v in the graph G − (S \ {u, v}). The exponential independence number alpha_e (G) of G is the maximum order of an exponentially independent set in G. In this work we present several bounds on this parameter and highlight some of the many related open problems. In particular, we prove that subcubic graphs of order n have exponentially independent sets of order $\Omega (n/ log 2 (n))$, that the infinite cubic tree has no exponentially independent set of positive density, and that subcubic trees of order n have exponentially independent sets of order (n + 3)/4.

joint work with D. Rautenbach and J. Pardey, Ulm University

Date and time: 20/05/2021 at 14:30 (Paris time)

Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p