2021/02/08 by Abdelamin Laouar, Laouar, Abdelamin, Isma Bouchemakh +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications
paper · doi:10.48550/arxiv.2102.04094
openalex publication_date 2021/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An independent broadcast on a graph G is a function f: V \longrightarrow \0,…,\rm 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≤ \lfloor(n)/(2) \rfloor, 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).