Bounds on broadcast time in well-connected graphs
Discrete Applied Mathematics · 2026-03 · 382 · 83-90
DOI: 10.1016/j.dam.2025.11.013 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2026-03. Verfasst von Ararat Harutyunyan und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 36 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada, French National Research Agency.
Abstract (Originalsprache)
Given a graph G , the broadcast time b ( G ) of G is the least number of time units required to disseminate one piece of information starting at an arbitrary originating vertex in G , where each transmission takes one time unit and each informed vertex can transmit the message to one of its neighbors at any time. We initiate the study of finding upper bounds on broadcast time b ( G ) in highly connected graphs. In particular, we give upper bounds on b ( G ) for k -connected graphs and graphs with a large minimum degree. We prove that b ( G ) ≤ ⌈ log k ⌉ + ⌈ nk ⌉ − 1 for all k -connected graphs. For many families of graphs this bound is tight. We also show that if the minimum degree of G is at least n/ 2, then b ( G ) ≤ ⌈ log n ⌉ + 3 time, and derive various similar upper bounds on graphs with large minimum degree. Finally, we discuss an open problem that relates the broadcast time of a graph with its minimum degree, when the latter is small.
Förderung
- Natural Sciences and Engineering Research Council of Canada
- French National Research Agency
Zitieren
APA
Harutyunyan, A., Harutyunyan, H. A., & Khanlari, A. (2026). Bounds on broadcast time in well-connected graphs. Discrete Applied Mathematics, 382, 83-90. https://doi.org/10.1016/j.dam.2025.11.013
Vancouver
Harutyunyan A, Harutyunyan HA, Khanlari A. Bounds on broadcast time in well-connected graphs. Discrete Applied Mathematics. 2026;382:83-90. doi:10.1016/j.dam.2025.11.013
BibTeX
@article{Harutyunyan2026,
author = {Harutyunyan, Ararat and Harutyunyan, Hovhannes A. and Khanlari, Aram},
title = {Bounds on broadcast time in well-connected graphs},
journal = {Discrete Applied Mathematics},
year = {2026},
volume = {382},
pages = {83--90},
doi = {10.1016/j.dam.2025.11.013}
}
EUVIMED