EUVIMEDEUVIMED entdecken
Crossref

Bounds on broadcast time in well-connected graphs

Ararat Harutyunyan, Hovhannes A. Harutyunyan, Aram Khanlari

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →