The Study of (T,R) Broadcast Domination and Related Labeling Problems on Graphs

Project Details


Due to a practical resource sharing problem, Blessing, Johnson, Mauretour, and Inskoconsider a variation of the domination problem which they call the (t,r) broadcast dominationproblem recently. They collect a vertex subset D that every vertex v in D can get a completeresource, using t to weight. Moreover, the vertex v in D can offer partial resource, using t-i toweight, to the vertex u with d(u,v)=i < t, and offer no resource, using 0 to weight, to othersvertices which have the distance at least t with v. For each vertex in the graph, the totalweight of the vertex must be at least r with 1≦r≦t. They determine the exact values of (t,r)broadcast domination number only for small grid graphs with t≦3. They also give upperbounds for large grid graphs with t≦3. Actually, I have studied this problem for t=r=3 inNSC 96-2115-M-008-011. On the basis of my past work, I can determine the complexity andgive some exact values in this topic. To complete the previous work, I will also study therelated L(p,q)-labeling problems in edge-path-replacement graphs.
Effective start/end date1/08/1631/07/17


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.