Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
New Lower Bounds on Broadcast Function
verfasst von : Hayk Grigoryan, Hovhannes A. Harutyunyan
Erschienen in: Algorithmic Aspects in Information and Management
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper studies the broadcast function
B
(
n
). We consider the possible vertex degrees and possible connections between vertices of different degrees in graphs with
$b(G) = {\left\lceil\log_2 n\right\rceil}$
. Using this, we present improved lower bounds on
B
(
n
) when
n
= 2
k
− 2
p
and
n
= 2
k
− 2
p
+ 1 (3 ≤
p
<
k
). Also, we prove that
B
(24) ≥ 36 for graphs with maximum vertex degree at most 4.