On the Broadcast Independence Number of Circulant Graphs
share
An independent broadcast on a graph G is a function f: V ⟶{0,…, diam(G)} such that (i) f(v)≤ e(v) for every vertex v∈ V(G), where diam(G) denotes the diameter of G and e(v) the eccentricity of vertex v, and (ii) d(u,v) > max{f(u), f(v)} for every two distinct vertices u and v with f(u)f(v)>0. The broadcast independence number β_b(G) of G is then the maximum value of ∑_v ∈ V f(v), taken over all independent broadcasts on G. We prove that every circulant graph of the form C(n;1,a), 3≤ a≤⌊n/2⌋, admits an optimal 2-bounded independent broadcast, that is, an independent broadcast f satisfying f(v)≤ 2 for every vertex v, except when n=2a+1, or n=2a and a is even. We then determine the broadcast independence number of various classes of such circulant graphs, and prove that, for most of these classes, the equality β_b(C(n;1,a)) = α(C(n;1,a)) holds, where α(C(n;1,a)) denotes the independence number of C(n;1,a).
READ FULL TEXT