Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Hoepner, Julia Ingrid
University of Victoria
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Maximum boundary independent broadcasts in graphs and trees Hoepner, Julia Ingrid; MacGillivray, Gary; Mynhardt, Christina
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 2 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.2.1

Abstract

A broadcast on a connected graph G is a function f : V(G)→{0, 1, ...,  diam(G)} such that f(v)≤e(v) (the eccentricity of v) for all v ∈ V. If dG(u, v)≥f(u)+f(v) for any pair of vertices u, v with f(u)>0 and f(v)>0, the broadcast is said to be boundary independent.We show that the maximum weight αbn(G) of a boundary independent broadcast can be bounded in terms of the independence number α(G), and prove that the maximum boundary independent broadcast problem is NP-hard. We investigate bounds on αbn(T) when T is a tree in terms of its order and the number of vertices of degree at least 3, and determine a sharp upper bound on αbn(T) when T is a caterpillar, giving αbn(T) exactly for certain families of caterpillars. We conclude by describing a polynomial-time algorithm to determine αbn(T) for a given tree T. 
Co-Authors MacGillivray, Gary Mynhardt, Christina