More broadcast graphs

DOI10.1016/S0166-218X(99)00108-0MaRDI QIDQ1961235zbMATH OpenOpenAlexFDO

Authors Hovhannes A. Harutyunyan, Arthur L. Liestman

Publication date 8 May 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00108-0

zbMATH Keywords

broadcast graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

Let \(G\) be a graph. Broadcasting in \(G\) is the process of spreading information from one vertex, which knows the information, throughout \(G\) so that, in each time unit, any vertex which knows the information can pass it to at most one of its neighbours. Denote by \(B(n)\) the minimum number of edges over all graphs of order \(n\) which allow any vertex to broadcast in time \(\left\lceil \log n\right\rceil \). In the paper a new upper bound on \(B(n)\) is provided for some values of \(n\).

Recommendations

• A new construction of broadcast graphs
• A new construction of broadcast graphs
• Lower bounds for the size in four families of minimum broadcast graphs
• A new method for constructing minimal broadcast networks
• A minimum broadcast graph on 26 vertices

Cites work

• A minimum broadcast graph on 63 vertices
• A new method for constructing minimal broadcast networks
• A Note on the Dimensionality of Modified Knödel Graphs
• A survey of gossiping and broadcasting in communication networks
• Antepenultimate broadcasting
• Broadcasting in Bounded Degree Graphs
• Compound constructions of broadcast networks
• scientific article; zbMATH DE number 4141826 (Why is no real title available?)
• scientific article; zbMATH DE number 3702701 (Why is no real title available?)
• scientific article; zbMATH DE number 177869 (Why is no real title available?)
• scientific article; zbMATH DE number 961881 (Why is no real title available?)
• Lower bounds for the size in four families of minimum broadcast graphs
• Minimal broadcast networks
• Minimum broadcast graphs
• New gossips and telephones
• On the construction of minimal broadcast networks
• Some minimum broadcast graphs
• Sparse broadcast graphs
• Tight Bounds on Mimimum Broadcast Networks

Cited in

(30)

• Set to set broadcasting in communication networks
• The broadcast function value \(B(23)\) is \(33\) or \(34\).
• On linear-time data dissemination in dynamic rooted trees
• Sparse hypercube -- a minimal \(k\)-line broadcast graph.
• Broadcast time and connectivity
• Lower bounds for the size in four families of minimum broadcast graphs
• The shortest path problem in the Knödel graph
• The complexity of finding a broadcast center
• A new construction of broadcast graphs
• Efficient construction of broadcast graphs
• Diametral broadcast graphs
• Binary linear programming models for robust broadcasting in communication networks
• A new construction of broadcast graphs
• Broadcast graphs using new dimensional broadcast schemes for Knödel graphs
• Broadcasting in Sierpinski gasket graphs
• A COMPOUNDING ALGORITHM FOR 1-FAULT TOLERANT BROADCAST NETWORKS
• scientific article; zbMATH DE number 1191227 (Why is no real title available?)
• Tight lower bounds on broadcast function for n = 24 and 25
• Upper bounds on the broadcast function using minimum dominating sets
• Total domination in cubic Knodel graphs
• A new method for constructing minimal broadcast networks
• A minimum broadcast graph on 26 vertices
• Broadcast graphs using new dimensional broadcast schemes for Knödel graphs
• On broadcast schemes of Knödel graphs
• Broadcast graph is NP-complete
• On time-relaxed broadcasting networks
• Broadcast schemes of hypercubes
• All sequential dimensional broadcast schemes in Knödel graphs
• On the number of broadcast schemes in networks
• Broadcasting from multiple originators

This page was built for publication: More broadcast graphs

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