Boundary and Hearing Independent Broadcasts in Graphs and Trees

arXiv2305.03516MaRDI QIDQ6435489FDOQ6435489

Authors: Jules Hoepner, Gary MacGillivray, Christina M. Mynhardt

Publication date: 4 May 2023

Abstract: A broadcast on a connected graph G with vertex set V(G) is a function

f : V (G) i g h t a r r o w 0, 1, ..., e x t d i a m (G)

such that

f (v) l e q e (v)

(the eccentricity of

v

) for all

v i n V

. A vertex

v

is said to be broadcasting if

f (v) > 0

, with the set of all such vertices denoted

V_{f}^{+}

. A vertex

u

hears

f

from

v i n V_{f}^{+}

if

d_{G} (u, v) l e q f (v)

. The broadcast

f

is hearing independent if no broadcasting vertex hears another. If, in addition, any vertex

u

that hears

f

from multiple broadcasting vertices satisfies

f (v) l e q d_{G} (u, v)

for all

v i n V_{f}^{+}

, the broadcast is said to be boundary independent. The cost of

f

is

s i g m a (f) = s u m_{v i n V (G)} f (v)

. The minimum cost of a maximal boundary independent broadcast on G, called the lower bn-independence number, is denoted

i_{b n} (G)

. The lower h-independence number

i_{h} (G)

is defined analogously for hearing independent broadcasts. We prove that

i_{b n} (G) l e q i_{h} (G)

for all G and show that

i_{h} (G) / i_{b n} (G)

is bounded. For both parameters, we show that the lower bn-independence number (h-independence number) of a connected graph G equals the minimum lower bn-independence number (h-independence number) among those of its spanning trees. We further study the maximum cost of boundary independent broadcasts, denoted

a l p h a_{b n} (G)

. We show

a l p h a_{b n} (G)

can be bounded in terms of the independence number

a l p h a (G)

, and prove that the maximum bn-independent broadcast problem is NP-hard by a reduction from the independent set problem to an instance of the maximum bn-independent broadcast problem. With particular interest in caterpillars, we investigate bounds on

a l p h a_{b n} (T)

when T is a tree in terms of its order and the number of vertices of degree at least 3, known as the branch vertices of T. We conclude by describing a polynomial-time algorithm to determine

a l p h a_{b n} (T)

for a given tree T.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

This page was built for publication: Boundary and Hearing Independent Broadcasts in Graphs and Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435489)