References:

[1] R. Ahlswede, L. Gargano, H. S. Haroutunian, and L. H. Khachatrian. Fault-tolerant minimum broadcast networks. Networks, 27:293–307, 1996.
[2] P. Alikhanifard, M. Fakharan, and H. A. Harutyunyan. Broadcast schemes of hypercubes. Journal of Graph Algorithms and Applications, 29(1):125–134, 2025.
[3] A. Aminian, S. Kamali, S. M. Seyed-Javadi, and Sumedha. On the complexity of telephone broadcasting: From cacti to bounded pathwidth graphs. International Colloquium on Automata, Languages, and Programming, Proceedings of ICALP, 2025.
[4] Anonymous. Improved approximation for broadcasting in k-cycle graphs. 42nd Conference on Very Important Topics (CVIT 2016), Leibniz International Proceedings in Informatics (LIPIcs), 23:1–14, 2025.
[5] A. Averbuch, R. H. Shabtai, and Y. Roditty. Efficient construction of broadcast graphs. Discrete Applied Mathematics, 171:9–14, 2014.
[6] S. M. Banik, S. Radhakrishnan, and C. N. Sekharan. Multicast routing with delay and delay variation constraints for collaborative applications on overlay networks. IEEE Transactions on Parallel and Distributed Systems, 18(3):421–431, 2007. 141
[7] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber. Multicasting in heterogeneous networks. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC ’98), pages 448–453, 1998.
[8] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber. Message multicasting in heterogeneous networks. SIAM Journal on Computing, 30(2):347–358, 2000.
[9] G. Barsky, H. Grigoryan, and H. A. Harutyunyan. Tight lower bounds on broadcast function for n= 24 and 25. Discrete Applied Mathematics, 175(1-3):109–114, 2014.
[10] H. Baumann, P. Fraigniaud, H. A. Harutyunyan, and R. de Verclos. The worst case behavior of randomized gossip. In International Conference on Theory and Applications of Models of Computation. Berlin, Heidelberg: Springer Berlin Heidelberg, 560:330–345, 2012.
[11] H. Baumann, P. Fraigniaud, H. A. Harutyunyan, and R. de Verclos. The worst case behavior of randomized gossip protocols. Theoretical Computer Science, 560:108– 120, 2014.
[12] R. Beier and J. F. Sibeyn. A powerful heuristic for telephone gossiping. Citeseer, 2000.
[13] J. C. Bermond and C. Peyrat. De bruijn and kautz networks: a competitor for the hypercube? First European Workshop on Hypercube and Distributed Computers, page 279, 1989.
[14] J. C. Bermond, C. Peyrat, R. Peine, and E. St¨ohr. Broascasting in de bruijn networks. Congressus numerantium, 66:283–292, 1988.
[15] J. C. Bermond, P. Hell, A. L. Liestman, and J. G. Peters. Sparse broadcast graphs. Discrete applied mathematics, 36(2):97–130, 1992.
[16] J. C. Bermond, P. Fraigniaud, and J. G. Peters. Antepenultimate broadcasting. Networks, 26(3):125–137, 1995.
[17] J.-C. Bermond, H. A. Harutyunyan, A. L. Liestman, and S. Perennes. A note on the dimensionality of modified kn¨odel graphs. International Journal of Foundations of Computer Science, 8(2):109–116, 1997.
[18] P. Bhabak and H. A. Harutyunyan. Constant approximation for broadcasting in k-cycle graph. Sumit Ganguly and Ramesh Krishnamurti, editors, Algorithms and Discrete Applied Mathematics, pages 21–32, 2015.
[19] P. Bhabak, H. A. Harutyunyan, and S. Tanna. Broadcasting in harary-like graphs. IEEE 17th International Conference on Computational Science and Engineering, pages 1269–1276, 2014.
[20] P. Bhabak, H. A. Harutyunyan, and P. Kropf. Efficient broadcasting algorithm in harary-like networks. 46th International Conference on Parallel Processing Workshops (ICPPW), pages 162–170, 2017.
[21] L. Changhong, Z. Kemin, S. M. Mitchell, and A. Proskurowski. The broadcast function value b(23) is 33 or 34. Acta Mathematicae Applicatae Sinica, English Series 16, 3(2):329–331, 2000.
[22] S. C. Chau and A. L. Liestman. Constructing minimal broadcast networks. Journal of Combinatorial Information System Sciences, 10:110–122, 1985.
[23] M. J. Dinneen, M. R. Fellows, and V. Faber. Algebraic constructions of efficient broadcast networks. In International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes (AAECC ’91), pages 152–158. Springer, 1991.
[24] M. J. Dinneen, J. A. Ventura, M. C.Wilson, and G. Zakeri. Compound constructions of broadcast networks. Discrete applied mathematics, 93(2–3):205–232, 1999.
[25] Y. Egami, T. Gima, T. Hanaka, Y. Kobayashi, M. Lampis, V. Mitsou, E. Nemery,
Y. Otachi, M. Vasilakis, and D. Vaz. Broadcasting under structural restrictions. In
Proceedings of MFCS 2025, 2025.
[26] M. Elkin and G. Kortsarz. Combinatorial logarithmic approximation algorithm for
directed telephone broadcast problem. Proceedings of the 30th ACM Symposium on
Theory of Computing (STOC), pages 438–447, 2002.
[27] M. Elkin and G. Kortsarz. combinatorial logarithmic approximation algorithm for
the directed telephone broadcast problem. Thiry-Fourth Annual ACM Symposium on
Theory of Computing, STOC, 2:438–447, 2002.
[28] M. Elkin and G. Kortsarz. A combinatorial logarithmic approximation algorithm
for the directed telephone broadcast problem. SIAM journal on Computing, 35(3):
672–689, 2005.
[29] M. Elkin and G. Kortsarz. Sublogarithmic approximation for telephone multicast.
Journal of Computer and System Sciences, 72(4):648–659, 2006.
[30] M. Fakharan and H. A. Harutyunyan. On broadcast schemes of kn¨odel graphs. Parallel
Processing Letters, 34(03n04):2450009, 2024.
[31] M. Fakharan and H. A. Harutyunyan. Dimensional broadcast schemes for generalized
kn¨odel graphs. Parallel Processing Letters, 35(01n02):2550002, 2025.
[32] A. M. Farley. Minimal broadcast networks. Networks, 9(4):313–332, 1979.
144
[33] A. M. Farley and S. T. Hedetniemi. Broadcasting in grid graphs. In Proceedings 9th
S.E. Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica,
pages 275–288, 1978.
[34] A. M. Farley, S. T. Hedetniemi, S. M. Mitchell, and A. Proskurowski. Minimum
broadcast graphs. Discrete Mathematics, 25(2):189–193, 1979.
[35] G. Fertin and A. Raspaud. A survey on kn¨odel graphs. Discrete Applied Mathematics,
137(2):173–195, 2004.
[36] G. Fertin, A. Raspaud, H. Schr¨oder, O. Sykora, and I. Vrto. Diameter of the kn¨odel
graph. In Graph-Theoretic Concepts in Computer Science (WG 2000), Lecture Notes
in Computer Science, 1928:149–160, 2000.
[37] F. V. Fomin, P. Fraigniaud, and P. A. Golovach. Parameterized complexity of broadcasting
in graphs. In Dani¨el Paulusma and Bernard Ries, editors, Graph-Theoretic
Concepts in Computer Science, Cham, Springer Nature Switzerland, 1928:334–347,
2023.
[38] F. V. Fomin, P. Fraigniaud, and P. A. Golovach. Parameterized complexity of broadcasting
in graphs. Theoretical Computer Science, 997:114508, 1928, 2024.
[39] P. Fraigniaud and E. Lazard. Methods and problems of communication in usual
networks. Discrete Applied Mathematics, 53(1-3):79–133, 1994.
[40] P. Fraigniaud and J. G. Peters. Minimum linear gossip graphs and maximal linear
(�, k)-gossip graphs. Networks: An International Journal, 38(3):150–162, 2001.
[41] P. Fraigniaud, A. L. Liestman, and D. Sotteau. Open problems. Parallel Proc. Lett.,
3:507–524, 1993.
145
[42] M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory
of np-completeness. W. H. Freeman and Co., USA, 1979.
[43] L. Gargano and U. Vaccaro. On the construction of minimal broadcast networks.
Networks, 19(6):673–689, 1989.
[44] M. Grigni and D. Peleg. Tight bounds on mimimum broadcast networks. SIAM
Journal on Discrete Mathematics, 4(2):207–222, 1991.
[45] H. Grigoryan and H. A. Harutyunyan. New lower bounds on broadcast function.
Algorithmic Aspects in Information and Management, 8546:174184, 2014.
[46] H. Grigoryan and H. A. Harutyunyan. The shortest path problem in the kn¨odel graph.
Journal of Discrete Algorithms, 31:40–47, 2015.
[47] A. H. Harutyunyan, N. Hovhannisyan, and R. Magithiya. Deep heuristic for broadcasting
in arbitrary networks. 21st international symposium on parallel and distributed
computing (ispdc), pages 1–8, 2022.
[48] H. A. Harutyunyan. Minimum multiple message broadcast graphs. Networks, 47(4):
218–224, 2006.
[49] H. A. Harutyunyan. An efficient vertex addition method for broadcast networks.
Internet Mathematics, 5(3):211–225, 2008.
[50] H. A. Harutyunyan and Z. Li. A new construction of broadcast graphs. Conference
on Algorithms and Discrete Applied Mathematics, 9602:201–211, 2016.
[51] H. A. Harutyunyan and Z. Li. Broadcast graphs using new dimensional broadcast
schemes for kn¨odel graphs. Discrete Applied Mathematics, 336:56–67, 2023.
146
[52] H. A. Harutyunyan and A. L. Liestman. More broadcast graphs. Discrete Applied
Mathematics, 98(1):81–102, 1999.
[53] H. A. Harutyunyan and A. L. Liestman. Improved upper and lower bounds for k-
broadcasting. Networks, 37(2):94–101, 2001.
[54] H. A. Harutyunyan and A. L. Liestman. On the monotonicity of the broadcast function.
Discrete Mathematics, 262(1–3):149–157, 2003.
[55] H. A. Harutyunyan and A. L. Liestman. Upper bounds on the broadcast function
using minimum dominating sets. Discrete Mathematics, 312(20):2992–2996, 2012.
[56] H. A. Harutyunyan and E. Maraachlian. Linear algorithm for broadcasting in unicyclic
graphs. In International Computing and Combinatorics Conference (COCOON
’07), pages 372–382. Springer, 2007.
[57] H. A. Harutyunyan and E. Maraachlian. On broadcasting in unicyclic graphs. Journal
of combinatorial optimization, 16(3):307–322, 2008.
[58] H. A. Harutyunyan and B. Shao. An efficient heuristic for broadcasting in networks.
Journal of Parallel and Distributed Computing, 66(1):68–76, 2006.
[59] H. A. Harutyunyan and M. Terzian. Directional core selection approach and dynamic
tree reorganization for delay and delay variation multicast routing. International
Journal of Communication Systems, 31(4):178–182, 2018.
[60] H. A. Harutyunyan, S. Kamali, and T. Moradian. Multi-shared-trees based multicasting
in mesh-connected networks. Proceedings of the International Conference
on Parallel and Distributed Processing Techniques and Applications, PDPTA, pages
178–182, 2008.
147
[61] H. A. Harutyunyan, R. Katragadda, and C. D. Morosan. Efficient heuristic for multicasting
in arbitrary networks. 23rd International Conference on Advanced Information
Networking and Applications, AINA 2009, Workshops Proceedings, Bradford,
United Kingdom, pages 61–66, 2009.
[62] H. A. Harutyunyan, A. Liestman, and B. Shao. A linear algorithm for finding the
k-broadcast center of a tree. Networks, 53(3):287–292, 2009.
[63] H. A. Harutyunyan, A. L. Liestman, J. G. Peters, and Richards D. Broadcasting and
gossiping. In Handbook of Graph Theory, pages 1477–1494. Chapman and Hall,
2013.
[64] H. A. Harutyunyan, N. Hovhannisyan, and E. Maraachlian. Broadcasting in chains
of rings. Fourteenth International Conference on Ubiquitous and Future Networks
(ICUFN), 2023.
[65] S. M. Hedetniemi, S. T. Hedetniemi, and A. L. Liestman. A survey of gossiping and
broadcasting in communication networks. Networks, 18(4):319–349, 1988.
[66] M. C. Heydemann, S. Marlin, and S. Perennes. Rotational Cayley graphs on transposition
generated groups. Electronic Notes in Discrete Mathematics, 5:177–180,
2000.
[67] M. C. Heydemann, S. Marlin, and S. Perennes. Complete rotations in cayley graphs.
European Journal of Combinatorics, 22(2):179–196, 2001.
[68] J. Hromkoviˇc, R. Klasing, B. Monien, and R. Peine. Dissemination of information
in interconnection networks (broadcasting & gossiping). In Combinatorial network
theory, pages 125–212. Springer, 1996.
148
[69] J. Hromkoviˇc, R. Klasing, A. Pelc, P. Ruzicka, and W. Unger. Dissemination of
information in communication networks: broadcasting, gossiping, leader election,
and fault-tolerance. In Texts in Theoretical Computer Science. An EATCS Series.
Springer, 2005.
[70] L. H. Khachatrian and H. S. Haroutunian. Construction of new classes of minimal
broadcast networks. In Conference on Coding Theory, Armenia, pages 69–77, 1990.
[71] R. Klasing, B. Monien, R. Peine, and E. St¨ohr. Broadcasting in butterfly and de
bruijn networks. Discrete Applied Mathematics, 53:183–197, 1994.
[72] W. Kn¨odel. New gossips and telephones. Discrete Mathematics, 13:95, 1975.
[73] J. C. K¨onig and E. Lazard. Minimum k-broadcast graphs. Discrete Applied Mathematics,
53(1-3):199–209, 2009.
[74] G. Kortsarz and D. Peleg. Approximation algorithms for minimum-time broadcast.
SIAM Journal on Discrete Mathematics, 8(3):401–427, 1995.
[75] R. Labahn. A minimum broadcast graph on 63 vertices. Discrete Applied Mathematics,
53(1–3):247–250, 1994.
[76] A. L. Liestman and J. G. Peters. Broadcast networks of bounded degree. SIAM
journal on Discrete Mathematics, 1(4):531–540, 1988.
[77] A. L. Liestman and N. Przulj. Minimum average time broadcast graphs. Parallel
processing letters, 8(02):139–147, 1998.
[78] C. Lund and M. Yannakakis. On the hardness of approximating minimization problems.
Journal of the ACM (JACM), 41(5):960–981, 1994.
149
[79] M. Maheo and J.-F. Sacl´e. Some minimum broadcast graphs. Discrete Applied
Mathematics, 53(1-3):275–285, 1994.
[80] E. Maraachlian. Optimal broadcasting in treelike graphs. PhD thesis, Concordia
University, 2010.
[81] D. C. Meliksetian and C. R. Chen. Communication aspects of the cube connected
cycles. International Conference on Parallel Processing (ICPP), 1:579–580, 1990.
[82] M. Middendorf. Minimum broadcast time is np-complete for 3-regular planar graphs
and deadline 2. Information Processing Letters, 46(6):281–287, 1993.
[83] S. Mitchell and S. Hedetniemi. A census of minimum broadcast graphs. Journal of
Combinatorial Information System Sciences, 5:141–151, 1980.
[84] S. R. Musawi and E. Nazari. Diameter of general kn¨odel graphs. Fundamenta
Informaticae, 190(1):47–62, 2023.
[85] J.-H. Park and K.-Y. Chwa. Recursive circulant: A new topology for multicomputer
networks. In Proceedings of the International Symposium on Parallel Architectures,
Algorithms and Networks (ISPAN ’94), pages 73–80. IEEE, 1994.
[86] Proskurowski. Minimum broadcast trees. IEEE Transactions on Computers, 30(5):
363–366, 1981.
[87] R. Ravi. Rapid rumor ramification: Approximating the minimum broadcast time. In
Proceedings 35th Annual Symposium on Foundations of Computer Science (FOCS
’94), pages 202–213. IEEE, 1994.
[88] J.-F. Sacl´e. Lower bounds for the size in four families of minimum broadcast graphs.
Discrete Mathematics, 150(1-3):359–369, 1996.
150
[89] P. Scheuermann and M. Edelberg. Optimal broadcasting in point-to-point computer
networks. Department of Electrical Engineering and Computer Science, Northwestern
University, Evanston, IL, Technical Report, 1981.
[90] P. Scheuermann and G. Wu. Heuristic algorithms for broadcasting in point-to-point
computer networks. IEEE Transactions on Computers, 33(09):804–811, 1984.
[91] C. Schindelhauer. On the inapproximability of broadcasting time. In International
Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX
’00), pages 226–237. Springer, 2000.
[92] B. Shao. On K-broadcasting in Graphs. PhD thesis, Concordia University, 2006.
[93] P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi. Information dissemination in
trees. SIAM Journal on Computing, 10(4):692–701, 1981.
[94] E. Stohr. Broadcasting in the butterfly network. Information Processing Letters, 39:
41–43, 1991.
[95] E. Stohr. On the broadcast time of the butterfly network. 17th International Workshop
on Graphtheoretic Concepts in Computer Science, pages 226–229, 1991.
[96] P. Tale. Double exponential lower bound for telephone broadcast. arXiv preprint
arXiv:2403.03501, 2024.
[97] P. Tale. Telephone broadcast on graphs of treewidth two. Theoretical Computer
Science, 1045:115282, 2025.
[98] M. Cˇ evnik and J. Zˇ erovnik. Broadcasting on cactus graphs. Journal of Combinatorial
Optimization, 33(1):292–316, 2017.
151
[99] M. X. Weng and J. A. Ventura. A doubling procedure for constructing minimal
broadcast networks. Telecommunication Systems, 3:259–293, 1994.
[100] J. Xiao and X. Wang. A research on minimum broadcast graphs. Chinese Journal
of Computers, 11:99–105, 1988.
[101] J. Xu and Z. Li. Broadcast graph is np-complete. In Conference on Algorithms and
Discrete Applied Mathematics, Cham: Springer Nature Switzerland, pages 343–357,
2025.
[102] J.-g. Zhou and K.-m. Zhang. A minimum broadcast graph on 26 vertices. Applied
mathematics letters, 14(8):1023–1026, 2001.