
arXiv: 1809.09288
An independent broadcast on a connected graph $G$ is a function $f:V(G)\to \mathbb{N}_0$ such that, for every vertex $x$ of $G$, the value $f(x)$ is at most the eccentricity of $x$ in $G$, and $f(x)>0$ implies that $f(y)=0$ for every vertex $y$ of $G$ within distance at most $f(x)$ from $x$. The broadcast independence number $α_b(G)$ of $G$ is the largest weight $\sum\limits_{x\in V(G)}f(x)$ of an independent broadcast $f$ on $G$. Clearly, $α_b(G)$ is at least the independence number $α(G)$ for every connected graph $G$. Our main result implies $α_b(G)\leq 4α(G)$. We prove a tight inequality and characterize all extremal graphs.
Connectivity, Extremal problems in graph theory, independence, Independence, Signed and weighted graphs, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), broadcast independence, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Broadcast independence
Connectivity, Extremal problems in graph theory, independence, Independence, Signed and weighted graphs, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), broadcast independence, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Broadcast independence
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
