# 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