Dominating Broadcast and Multipacking in Specific Graph: A Case Study on Cycle Graphs and Sunlet Graphs

Overview

Domination in graphs has long been studied. It is applied to signal distribution problem. For example, telecommunication companies want to spread the signal from broadcast stations by transmitting varying signal strength to all receiving stations. However, broadcast stations with stronger signal are generally more expensive. It is quite difficult to distribute broadcast station and its strength so that each receiving station can get signal from some broadcast stations with minimal signal cost. The total of signal cost is called ?_b-dominating broadcast number. Moreover, I considered a specific setting where each station must receive no more than k signals from some selected stations with distribution strength k. The maximum number of such selected stations was called multipacking number. I studied some specific graphs that are cycle graphs, sunlet graphs, first order generalized sunlet graphs and the composition of a path graph and a cycle graph. I try to find the ?_b-dominating broadcast number and the multipacking number of these specific graphs by using mathematical methods and the background propositions especially those introduced by L.E.Teshima (2012).

Competition history

• ISEF 2015 Category not listed · Entry MATH041I

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.