# Domination broadcast: A case study on a combination of cycle graph and
sunlet graph

Sivakorn Sanguanmoo
Department of Mathematics
University of Wisconsin-Madison
<EMAIL_ADDRESS>

###### Abstract

Domination in graphs has long been studied and 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. This problem can be interpreted in a term of graph
theory. Assume that broadcast companies need to spread the signal in graphs by
using broadcast stations with varying signal strength so that the signal could
be sent to all the vertices. However, broadcast stations with stronger signal
are generally more expensive. The distribution of signal was configured to
cover all stations with minimum total cost of signal called the
$\gamma_{b}-$dominating broadcast number. This paper shows another proof of
the $\gamma_{b}-$dominating broadcast number of cycle graphs and sunlet graphs
as a foundation for the further result. I also consider the
$\gamma_{b}-$dominating broadcast number of a generalized version of sunlet
graphs whose vertices on the cycle are equally extended by the path, called
the sunlet graph with degree $n$. To obtain the optimal cost of the signal
distribution for this extended version, we show that it is sufficient to use
only one broadcast station at a vertex on the cycle with the signal cost equal
to the radius of the sunlet graph with degree $n$.

##  1 Introduction

Daily life network communication has been found problematic. Distribution
network is a part of network communication. However, the distribution of
signal is not covering the target areas. Also, the strong signal distributed
to cover the target areas is quite expensive. In this study, we examined
relation of network by means of graphs. We examined how to construct signal
stations that could distribute signal to cover the target areas, where each of
which has determined distribution strength with minimum total cost of signal
sending. We considered all of the areas as a set of vertices, where two
vertices were joined with an edge when the two areas were neighbor. All of
vertices and edges were called A graph $G$. All of the signal stations that
could satisfy the previous conditions were represented by broadcasts
dominating set $S$ so we called the cardinality of set $S$ as $\gamma_{b}-$
broadcast number of graph $G$ or $\gamma_{b}(G)$.

Some specific graphs of this study represented cities in general. For example,
a sunlet graph is a graph representing the center and each center connects to
another which is like an urban city. Also, pendant vertices represent cities
in the countryside. Therefore, studying a function $\gamma_{b}$ of specific
graphs, such as cycle graph $(C_{n})$, sunlet graph $(S_{n})$, and
sunlet$-n\textemdash$, is going to be useful for broadcasting signal in the
real world.

##  2 Term in Graph Theory

######  Term 1.

The distance $d(u,v)$ between vertices $u$ and $v$ of a graph $G$ is the
length of a shortest path between $u$ and $v$

Example

Figure 1: The example of graph $G$

According to Term 1, $d(A,B)=1,d(A,D)=2$ and $d(B,E)=3$

######  Term 2.

Eccentricity of a vertex v or $e(v)$ is the maximum distance of d(u,v) among
all vertices $u$ in a graph G. Formally, $e(v)=max\\{d(u,v)|u\in V(G)\\}$.

######  Term 3.

Radius of a graph $G$ or $rad(G)$ is the minimum eccentricity value of a
vertex $v$ among all vertices $v$ in a graph $G$. Formally,
$rad(G)=min\\{e(v)|v\in V(G)\\}$.

######  Term 4.

Diameter of a graph $G$ or $diam(G)$ is maximum eccentricity value of a vertex
$v$ among all vertices $v$ in a graph $G$. Formally, $diam(G)=max\\{e(v)|v\in
V(G)\\}$.

From Figure 1, $e(A)=max\\{d(A,B),d(A,C),d(A,D),d(A,E)\\}=3$. Similarly,
$e(B)=3,e(C)=2,e(D)=2$, and $e(E)=3$, so $rad(G)=2$ and $diam(G)=3$

##  3 Definition

###  3.1 Variations graph of cycle graph and sunlet graph

######  Definition 1.

The path or $P_{n}$ is a graph which consists of $n$ vertices lying on a
straight line where $n$ is a natural number. Formally,
$V(P_{n})=\\{v_{1},v_{2},...,v_{n}\\},E(P_{n})=\\{v_{i}v_{i+1}|i\in\\{1,2,...,n-1\\}\\}$

Figure 2: graph $P_{9}$

######  Definition 2.

The cycle or $C_{n}$ is a graph which consists of $n$ vertices,
$v_{1},v_{2},...,v_{n}$, and edges,
$v_{1}v_{2},v_{2}v_{3},...,v_{n-1}v_{n},v_{n}v_{1}$

Figure 3: graph $C_{6}$

######  Definition 3.

The sunlet or $S_{n}$ is a graph on vertices obtained by attaching pendant
edges to a cycle graph $C_{n}$.

Figure 4: graph $S_{8}$

######  Definition 4 ([1]).

$m-$ Sunlet degree $n$ or $S_{m}^{n}$ is a graph which consists of $C_{m}$ and
straight path length $n$ $(P_{n})$ extended from all vertices of $C_{m}$ of
where $m,n$ are positive integers such that $m\geq 3,n\geq 1$. We call each
vertex of $C_{m}$ as a base vertex, each $P_{n}$ as a branch, vertices on
$P_{n}$ as pendant vertices, and an outmost pendant vertex as a leaf vertex.

Figure 5: graph $S_{6}^{4}$

###  3.2 Dominating Broadcast [4],[5]

######  Definition 5.

A broadcast vertex $v$ with strength $m$ is a vertex which can send a signal
to vertices in the graph such that a vertex $u$ can receive a signal from $v$
if and only if $d(u,v)\leq m$, note that $u$ can send a signal to itself where
$m$ is a positive integer.

Figure 6: graph H with a broadcast vertex (the blue vertex) with signal
strength (the number beside the blue vertex) and vertices which can receive a
signal from the broadcast vertex (red vertices)

######  Definition 6.

Dominating broadcast function $f$ is a function from set of vertices to set of
positive integers including $0$ such that if a function $f$ value of a vertex
$u$ is $0$, $u$ is not a broadcast vertex. On the other hand, if a function
$f$ value of the vertex $u$ is $m\neq 0$, $u$ is a broadcast vertex with
strength $m$. The condition of this function is that all vertices of the graph
have to receive signals from at least one broadcast vertex.

######  Definition 7.

The cost of function $f$ is the total of signal strengths of broadcast
vertices in function $f$.

Figure 7: graph $H$ with the dominating broadcast function (two blue vertices
are broadcast vertices and a number beside each broadcast vertex is a signal
strength of that vertex).

######  Definition 8.

$\gamma_{b}-$ dominating broadcast function of graph $G$ is a dominating
broadcast function of $G$ which has the minimum cost. We call this minimum
cost as $\gamma_{b}$ of a graph $G$ or $\gamma_{b}(G)$

As we see in Figure 7, those two vertices with those signal strengths have the
minimum cost of dominating broadcast functions, so $\gamma_{b}(H)=3$.

######  Definition 9.

The efficient broadcast is the dominating broadcast such that each vertex can
receive a signal from only one broadcast vertex.

As we see in Figure 7, this is not the efficient broadcast because the vertex
between two broadcast vertices can receive signals from both broadcast
vertices.

##  4 Corollary

These following corollaries are essential corollaries for finding
$\gamma_{b}-$dominating broadcast function value of the cycle, the Sunlet, and
the Sunlet degree $n$.

######  Corollary 1 ([3]).

Every graph $G$ has a $\gamma_{b}-$ broadcast which is efficient.

This corollary is proved by D.J. Erwin. We will not show the proof but the
example for this corollary.

Figure 8: The $\gamma_{b}-$ dominating broadcast function of the graph $H$
which is efficient

From Figure 7, $\gamma_{b}(H)=3$. Therefore, the dominating broadcast function
in Figure 8 is the $\gamma_{b}-$ dominating broadcast function. Consider that
every vertex can receive a signal from only the blue vertex. Therefore, this
$\gamma_{b}-$ dominating broadcast function is efficient.

Consider Figure 8 that the efficient broadcast function which is also the
$\gamma_{b}-$ dominating broadcast function uses only one broadcast vertex.
However, it does not mean that every graph can use only one broadcast vertex
for the $\gamma_{b}-$ dominating broadcast function.

Figure 9: The $\gamma_{b}-$ dominating broadcast function of the graph $C_{6}$
which is efficient

For $C_{6}$, $\gamma_{b}(C_{6})=2$. If we let a signal strength to any vertex
for $2$, it cannot send a signal to all vertices in a graph. In this case, the
$\gamma_{b}-$ dominating broadcast function occurs by using at least two
vertices. The $\gamma_{b}-$ dominating broadcast function in Figure 9 is
efficient.

######  Corollary 2.

$rad(S_{m}^{n})=\lfloor\frac{m}{2}\rfloor+n$

###### Proof.

From Term 2, $rad(S_{m}^{n})=min\\{e(v)|v\in V(G)\\}$. We need to find a
vertex $v$ which has the minimum eccentricity value. We will prove that $v$
needs to be the base vertex. For the sake of contradiction, assume that $v$ is
the pendant vertex with its base vertex $u$. Consider the vertex $w$ which is
not on the branch consisting the vertex $v$. It is obvious that the shortest
path between $v$ and $w$ has to pass $u$. Therefore,

$\displaystyle d(v,w)=d(v,u)+d(u,w)>d(u,w)$

Figure 10: The graph $S_{6}^{3}$ with vertices $u,v,w,$ and $u^{\prime}$

Let $e(u)=d(u,u^{\prime})$ where $u^{\prime}$ is the vertex of the graph $G$.
Consider that $u^{\prime}$ and $u$ cannot be on the same branch; otherwise,
$d(u,u^{\prime})\leq n$, which is not true because the distance between $u$
and a leaf vertex on the different branch is more than $n$. Therefore,

$\displaystyle e(u)=d(u,u^{\prime})<d(v,u^{\prime})\leq e(v)$

, which contradicts with the minimality of $e(v)$ as desired.

We can conclude that $v$ has to be a base vertex, and the farthest vertex from
$v$ is the leaf vertex $t$ on the branch completely opposite to the vertex
$v$. Therefore,

$\displaystyle rad(S_{m}^{n})=e(v)=d(v,t)=\lfloor\frac{m}{2}\rfloor+n$

∎

Figure 11: The shortest path between $v$ and $t$ of the graph $S_{6}^{3}$

######  Corollary 3.

For every graph $G$, $\gamma_{b}(G)\leq rad(G)$

###### Proof.

From Term 2, $rad(G)=min\\{e(v)|v\in V(G)\\}$. Therefore, there is a vertex
$v^{\prime}$ such that $e(v^{\prime})=rad(G)$, which means that
$d(v^{\prime},u)\leq rad(G)$ for every vertex $v$. We can use $v^{\prime}$ as
a broadcast vertex with a strength $rad(G)$ to send a signal to all vertices
in the graph. Thus, $\gamma_{b}(G)\leq rad(G)$ as desired. ∎

######  Corollary 4 ([2]).

For every natural number $n$, $\gamma_{b}(P_{n})=\lceil\frac{n}{3}\rceil$

We will not show the proof, but we will introduce the standard pattern of
${\gamma}_{b}-$dominating broadcast function of $P_{n}$

######  Definition 10.

the standard pattern of ${\gamma}_{b}-$dominating broadcast functions of
$P_{n}$ is the ${\gamma}_{b}-$dominating broadcast function of $P_{n}$ with
vertices $v_{1},v_{2},...,v_{n}$ with following conditions

  * •

if $n=1$, then let $P_{1}$ be a broadcast vertex with a strength $1$.

  * •

if $n=2$, then let either $P_{1}$ or $P_{2}$ be a broadcast vertex a strength
$1$.

  * •

if $n=3k$ where $k$ is a natural number, then let $P_{2},P_{5},...,P_{3k-1}$
be broadcast vertices with a strength $1$

  * •

if $n=3k+1$ where $k$ is a natural number, then let either
$P_{1},P_{3},P_{6},...,P_{3k}$ or $P_{2},P_{4},P_{7},...,P_{3k+1}$ be
broadcast vertices with a strength $1$.

  * •

if $n=3k+2$ where $k$ is a natural number, then let $P_{2}$ be a broadcast
vertex with a strength $2$, and let $P_{7},P_{10},...,P_{3k+1}$ be broadcast
vertices with a strength $1$.

It is easy to see that the cost of those standard patterns function is
$\lceil\frac{n}{3}\rceil$. Thus, these functions are the
${\gamma}_{b}-$dominating broadcast function of $P_{n}$.

Figure 12: the standard pattern of ${\gamma}_{b}-$dominating broadcast
function of $P_{1},P_{2},...,P_{8}$

The significant property of the standard pattern of ${\gamma}_{b}-$dominating
broadcast functions of $P_{n}$ is that if we add "phantom vertices" on both
sides of $P_{n}$ and "phantom edges" to be the infinite path, those broadcast
vertices can send a signal to "phantom vertices" at most one vertex for each
side.

######  Corollary 5.

Let $G$ be a graph consisting of vertices $A$ and $B$, but $A$ is not adjacent
to $B$. Let $G^{\prime}$ be the same graph with $G$ but an external side $AB$.
Then, ${\gamma}_{b}(G^{\prime})\leq{\gamma}_{b}(G)$.

###### Proof.

This corollary is obvious because the ${\gamma}_{b}-$dominating broadcast
function of $G$ is a dominating broadcast function of $G^{\prime}$ because
adding edges does not interrupt signal sending. ∎

##  5 Main theorem

The main purpose of this research is to find $\gamma_{b}-$dominating broadcast
function value of $C_{n}$ and $S^{n}_{m}$.

######  Theorem 1.

$\gamma_{b}(C_{n})=\lceil\frac{n}{3}\rceil$ for each natural number $n\geq 3$

Figure 13: the cycle graph $C_{n}$

###### Proof.

Consider any dominating broadcast function $x$ of $C_{n}$. Let broadcast
vertices for the function $x$ are $P_{x_{1}},P_{x_{2}},...,P_{x_{k}}$ where
$k$ is the number of the broadcast vertices, and $x_{1},x_{2},...,x_{k}$ are
natural number in an ascending order. Let the strength of each $P_{x_{l}}$ be
$q_{l}$ for each natural number $l\in\\{1,2,..,k\\}$.

Figure 14: Signals from $P_{x_{l}}$ (blue vectors)

Consider that $P_{x_{l}}$ can send a signal to its clockwise direction for
$q_{l}$ vertices. Also, it can send a signal to its anticlockwise direction
for $q_{l}$ vertices. Therefore, $P_{x_{l}}$ can send a signal to
$q_{l}+q_{l}+1=2q_{l}+1$ vertices (including $P_{x_{l}}$ itself).

Because $x$ is a dominating broadcast function, every vertex can receive
signal at least once. Therefore,

$\displaystyle\sum_{l=1}^{k}{(2q_{l}+1)}\geq n$ $\displaystyle
2\sum_{l=1}^{k}{q_{l}}+k\geq n$
$\displaystyle\sum_{l=1}^{k}{q_{l}}\geq\frac{n-k}{2}$

Also, $q_{l}\geq 1$ for each natural number $k\in\\{1,2,..,k\\}$, so
$\sum_{l=1}^{k}{q_{l}}\geq k$. Thus,

$\displaystyle\sum_{l=1}^{k}{q_{l}}\geq max\\{\frac{n-k}{2},k\\}$

Consider $\frac{n-k}{2}+\frac{n-k}{2}+k=n$, from Pigeonhole’s principle,
$max\\{\frac{n-k}{2},k\\}\geq\lceil\frac{n}{3}\rceil$ Therefore,

$\displaystyle\sum_{l=1}^{k}{q_{l}}\geq\lceil\frac{n}{3}\rceil$

which means that the minimum cost of $C_{n}$ is at least
$\lceil\frac{n}{3}\rceil$. It is sufficient to find the example of the
$\gamma_{b}-$dominating broadcast function $x$ of $C_{n}$ with cost
$\lceil\frac{n}{3}\rceil$. We provide $3$ following cases.

Case $1$ $n=3k$ for some positive integer $k$

Let $P_{3},P_{6},...,P_{3k}$ are broadcast vertices such that signal strength
of each broadcast vertex is $1$. Therefore, the cost of this function is
$k=\lceil{\frac{n}{3}}\rceil$. Consider that $P_{3i+1}$ can receive a signal
from $P_{3i}$, and $P_{3i+2}$ can receive a signal from $P_{3i+3}$. Thus, this
dominating broadcast function can send a signal to cover all vertices in the
graph as desired.

Figure 15: an example of the $\gamma_{b}-$dominating function of $C_{3}$
(left) and $C_{6}$ (right)

Case $2$ $n=3k+1$ for some positive integer $k$

Let $P_{3},P_{6},...,P_{3k}$ and $P_{1}$ are broadcast vertices such that
signal strength of each broadcast vertex is $1$. Therefore, the cost of this
function is $k+1=\lceil{\frac{n}{3}}\rceil$. Consider that $P_{3i+1}$ can
receive a signal from $P_{3i}$, and $P_{3i+2}$ can receive a signal from
$P_{3i+3}$. Thus, this dominating broadcast function can send a signal to
cover all vertices in the graph as desired.

Figure 16: an example of the $\gamma_{b}-$dominating function of $C_{7}$
(left) and $C_{10}$ (right)

Case $3$ $n=3k+2$ for some positive integer $k$

Let $P_{3},P_{6},...,P_{3k}$ and $P_{1}$ are broadcast vertices such that
signal strength of each broadcast vertex is $1$. Therefore, the cost of this
function is $k+1=\lceil{\frac{n}{3}}\rceil$. Consider that $P_{3i+1}$ can
receive a signal from $P_{3i}$, and $P_{3i+2}$ can receive a signal from
$P_{3i+3}$. Finally, $P_{3k+2}$ can receive a signal from $P_{1}$. Thus, this
dominating broadcast function can send a signal to cover all vertices in the
graph as desired.

Figure 17: an example of the $\gamma_{b}-$dominating function of $C_{5}$
(left) and $C_{8}$ (right)

From all three cases, we can conclude that
$\gamma_{b}(C_{n})=\lceil\frac{n}{3}\rceil$ for each natural number $n\geq 3$
∎

######  Theorem 2.

$\gamma_{b}(S_{n})=\lceil\frac{n+1}{2}\rceil$ for each natural number $n\geq
3$

Figure 18: Sunlet graph $S_{8}$

###### Proof.

Consider any $\gamma_{b}-$dominating broadcast $x$, which is also efficient
broadcast.

######  Claim 1.

there is only one broadcast vertex for the efficent broadcast $x$.

###### Proof.

For the sake of contradiction, assume that there are at least two broadcast
vertices for the function $x$. Because the number of branches is finite, there
are two different broadcast vertices, $v_{1},v_{2}$, which locate on two
branches such that there is no another broadcast vertex on the short arc
between two branches.

It is obvious that $v_{1},v_{2}$ are on different branches; otherwise, $v_{1}$
can receive signals from both $v_{1}$ and $v_{2}$, which contradicts with the
property of the efficient broadcast function.

Figure 19: The shortest path between $v_{1}$ and $v_{2}$ (blue vertices)

Let vertices on the shortest path between $v_{1}$ and $v_{2}$ be
$v_{1},u_{1},u_{2},...,u_{k},$ and $v_{2}$ in this order. Consider that
$u_{1},u_{2},...,u_{k}$ cannot be pendant vertices because the degree of
pendant vertices is just $1$, so it is impossible to have a pendant vertex as
a vertex between the path.

By the definition, $u_{1},u_{2},...,u_{k}$ cannot receive from broadcast
vertices, except $v_{1},v_{2}$. Let $i\in\\{1,2,...,k\\}$ be the largest
positive integer such that $v_{1}$ can send a signal to $u_{i}$. Therefore,
$u_{i+1}$ cannot receive a signal from $v_{1}$, so the signal strength of
$v_{1}$ is $i$.

However, the distance between $v_{1}$ and the pendant vertex $u^{\prime}_{i}$
of the branch which consists of $u_{i}$ is $i+1$. Thus, $u^{\prime}_{i}$
cannot receive a signal from $v_{1}$. Therefore, $u^{\prime}_{i}$ has to
receive a signal from $v_{2}$. Consider that the only shortest path between
$u^{\prime}_{i}$ and $v_{2}$ consists of $u_{i}$, which means that $u_{i}$ can
receive a signal from $v_{2}$. We can conclude that $u_{i}$ can receive
signals from both $v_{1}$ and $v_{2}$, which contradicts with the definition
of the efficient broadcast, as desired. ∎

We know that the minimum cost of $\gamma_{b}-$ dominating broadcast occurs
when there is just one broadcast vertex. Thus, $rad(S_{n})=\gamma_{b}(S_{n})$.
Consider that $rad(S_{n})=\lceil\frac{n+1}{2}\rceil$, therefore,
$\gamma_{b}(S_{n})=\lceil\frac{n+1}{2}\rceil.$∎

.

Figure 20: The example of $\gamma_{b}-$ dominating broadcast of $S_{10}$

Next, we will consider Sunlet degree $n$ where its cycle graph is $C_{3}$

######  Theorem 3.

$\gamma_{b}(S^{m}_{3})=m+1$ for each natural number $m$

###### Proof.

Consider the $\gamma_{b}-$domianting broadcast $x$ which is also an efficient
broadcast. Let $X$ is a broadcast vertex with strength $k$, which can send a
signal to any base vertex. We will provide $2$ cases of $X$.

Case 1 $X$ can send a signal to exactly one base vertex.

Therefore, $X$ cannot be a base vertex, and the distance between $X$ and its
base vertex is exactly $k$. Then, the remaining vertices will be separated
into two paths as Figure 21 shown.

Figure 21: Two disconnected paths (in closed loops) in a case that $X$ can
send a signal to exactly one broadcast vertex

Therefore, the cost of this dominating function is
$k+\lceil\frac{m-k}{3}\rceil+\lceil\frac{2m+2}{3}\rceil$

$\displaystyle k+\lceil\frac{m-2k}{3}\rceil+\lceil\frac{2m+2}{3}\rceil$
$\displaystyle\geq\lceil k+\frac{m-2k}{3}+\frac{2m+2}{3}\rceil$
$\displaystyle=\lceil\frac{3m+k+2}{3}\rceil$
$\displaystyle\geq\lceil\frac{3m+3}{3}\rceil$
$\displaystyle=m+1=rad(S_{3}^{m})$

Case 2 $X$ can send a signal to at least two broadcast vertices.

Let the distance between $X$ and its base vertex is $l$. By symmetry, $X$ can
send a signal to all three broadcast vertices. Then, the remaining vertices
which cannot receive a signal from $X$ will be separated into three paths as
Figure 22 shown.

Figure 22: Three disconnected paths (in ovals) in a case that $X$ can send a
signal to at least two broadcast vertices

Therefore, the cost of this dominating function is
$k+\lceil\frac{m-k-l}{3}\rceil+2\lceil\frac{m-k+l+1}{3}\rceil$

$\displaystyle k+\lceil\frac{m-k-l}{3}\rceil+2\lceil\frac{m-k+l+1}{3}\rceil$
$\displaystyle\geq\lceil k+\frac{m-k-1}{3}+\frac{2(m-k+l+1)}{3}\rceil$
$\displaystyle=\lceil\frac{3m+2l+1}{3}\rceil$
$\displaystyle\geq\lceil\frac{3m+1}{3}\rceil$
$\displaystyle=m+1=rad(S_{3}^{m})$

Therefore, the minimum cost of dominating broadcast function of $S^{m}_{3}$ is
$rad(S_{3}^{m})$. Thus,

$\displaystyle\gamma_{b}(S^{m}_{3})=m+1$

∎

Next, we will use the idea of Theorem 2 and Theorem 3 for finding the
$\gamma_{b}-$dominating broadcast function value for a general case of Sunlet
degree $n$.

######  Theorem 4.

$\gamma_{b}(S^{n}_{m})=n+\lfloor\frac{m}{2}\rfloor$ for each natural number
$n\geq 1$ and $m\geq 3$

Figure 23: Graph $S^{6}_{3}$

###### Proof.

Let $P(i)$ represents the statement
"$\gamma_{b}(S^{n}_{i})=i+\lfloor\frac{n}{2}\rfloor$ for each natural number
$n\geq 1$," for each natural number $i\geq 3$. We will use the mathematical
induction on a natural number $n$.

For the base case, we need to prove $P(3)$ is true. By Theorem 4,

$\displaystyle\gamma_{b}(S^{n}_{3})=n+1=n+\lfloor\frac{3}{2}\rfloor$

For the induction case, we assume that $P(m-1)$ is true where $m$ is a
positive integer greater than or equal 4, and we need to prove that $P(m)$ is
true.

Let $A$ be a set of ${\gamma}_{b}-$ broadcast functions of $S^{n}_{m}$. Let
$A^{\prime}$ be a subset of the set $A$ such that for each ${\gamma}_{b}$\-
efficient broadcast function of $S^{n}_{m}$, all vertices that can send signal
to a base vertex are base vertices. Let $B\subseteq A$ such that each
${\gamma}_{b}-$ broadcast function in $B$ does not has base vertex which
receives a signal from two broadcast vertices. It is obvious that
$B\neq\emptyset$ because the efficient broadcast function is an element of $B$

######  Claim 2.

If $n>2$, there is no function in $B$ such that there is a broadcast vertex
$M$ which can send a signal to the nearest base vertex $N$, and its signal
strength is $n=d(M,N)$

###### Proof.

We will prove this claim by the sake of contradiction. Assume that there is a
broadcast vertex $M^{\prime}$ which can send a signal to the nearest base
vertex $N^{\prime}$, and its signal strength is
$n^{\prime}=d(M^{\prime},N^{\prime})$. Let the adjacent base vertices of
$N^{\prime}$ be $N^{\prime}_{1},N^{\prime}_{2}$.

Therefore, this broadcast vertex cannot send a signal to a base vertex other
than $N^{\prime}$. Also, there is no signal crossing over the branch
consisting of $M^{\prime},N^{\prime}$ because otherwise the signal can reach
$N^{\prime}$, which contradicts with the property of the set $B$. Therefore,
edges $N^{\prime}N^{\prime}_{1},N^{\prime}N^{\prime}_{2}$ are not be used for
a passing way for signals. Thus, we can cut these two edges, and the
$\gamma_{b}-$ dominating broadcast function value is still the same.

Consider that the new graph is two independent graphs: $P_{n+1}$ and the
remaining graph called $S^{\prime}$. By Corollary 4, $\gamma_{b}-$ dominating
broadcast function value of $P_{n+1}$ is $\lceil\frac{n+1}{3}\rceil$. It is
sufficient to find $\gamma_{b}-$ dominating broadcast function value of
$S^{\prime}$

Let $S^{\prime\prime}$ be the graph $S^{\prime}$ with an external side
$N^{\prime}_{1}N^{\prime}_{2}$. It can be observed that $S^{\prime\prime}$ is
a graph $S^{m}_{n-1}$. By Corollary 5 and $P(m-1)$,

$\displaystyle\gamma_{b}(S^{\prime})\geq\gamma_{b}(S^{\prime\prime})=\gamma_{b}(S^{n}_{m-1})=n+\lfloor\frac{m-1}{2}\rfloor$

Therefore,

$\displaystyle\gamma_{b}(S^{n}_{m})$
$\displaystyle=\lceil\frac{n+1}{3}\rceil+\gamma_{b}(S^{\prime})$
$\displaystyle\geq\lceil\frac{n+1}{3}\rceil+n+\lfloor\frac{m-1}{2}\rfloor$
$\displaystyle>n+\lfloor\frac{m}{2}\rfloor=rad(S_{m}^{n})$ ($n>2$)

, which contradicts with Corollary 4 as desired. ∎

However, if $n\leq 2$, the $\gamma_{b}-$dominating broadcast function value in
Claim 2 is equal to $rad(S_{m}^{n})$. Therefore, it is sufficient to proof
only in a case that there is no function in $B$ such that there is a broadcast
vertex $M$ which can send a signal to the nearest base vertex $N$, and its
signal strength is $n=d(M,N)$

######  Claim 3.

$A^{\prime}\neq\emptyset$

###### Proof.

We will prove this claim by the sake of contradiction. Assume that
$A^{\prime}$ is the empty set.

Given that $f$ is a function $B\rightarrow\mathbf{N}\cup\\{0\\}$, such that
$f(x)$ is equal to the number of base vertices that receive signal from non-
base vertex in the dominating broadcast $x\in B$.

It is easy to see that $B$ is a finite set. From the extremal principle, there
exists $x_{0}\in B$ such that $f(x_{0})$ is the lowest value of $f(x)$. $(*)$

Because $A^{\prime}$ is the empty set, $f(x)$ cannot be $0$, which means that
$f(x_{0})\neq 0$. Thus, there is a non-base vertex $M$ such that $M$ can send
signal to base vertices. Let $N$ be a base vertex which is closest to the
vertex $M$, and the distance between $N$ and $M$ is $k$

Assume that a signal strength at the vertex $M$ is $n$, and there are $y$
vertices on the branch containing M and N such that they do not lie between M
and N.

Figure 24: The difference between the dominating broadcast function $x_{0}$
(left) and the dominating broadcast $x_{1}$ (right)

We will consider another dominating broadcast function $x^{\prime}_{0}$ such
that $x^{\prime}_{0}$ and $x_{0}$ are the same, except vertices and their
strengths on the branch containing $M$ and $N$. In the new broadcast function,
the vertex $M$ is eliminated, and the vertex $N$ becomes a member of the
broadcast function set with signal strength $n-k$ instead. Moreover, by
Definition 10, pendant vertices that cannot receive signal from the vertex $N$
follow the standard pattern of ${\gamma}_{b}-$broadcast function.

If $y\geq n$, consider that a total of signal strengths in this branch for
${\gamma}_{b}-$ broadcast function $x_{0}$ is $n+\lceil\frac{y-n}{3}\rceil$,
and a total of signal strengths in this branch for broadcast function
$x^{\prime}_{0}$ is $n-k+\lceil\frac{y-n+k}{3}\rceil$.

$n-k+\lceil\frac{y-n+k}{3}\rceil=n+\lceil\frac{y-n-2k}{3}\rceil\leq
n+\lceil\frac{y-n}{3}\rceil$

If $y<n$,consider that a total of signal strengths in this branch for
${\gamma}_{b}-$ broadcast function $x_{0}$ is $n$, and a total of signal
strengths in this branch for the broadcast function $x^{\prime}_{0}$ is
$n-k+\lceil\frac{y-n+k}{3}\rceil$.

$n-k+\lceil\frac{y-n+k}{3}\rceil\leq n-k+\lceil\frac{k}{3}\rceil\leq n$

Therefore, the cost of $x^{\prime}_{0}$ is less than the cost of $x_{0}$,
which means that $x^{\prime}_{0}$ is also ${\gamma}_{b}-$broadcast function as
$x_{0}$ is. Consider that the distance between $N$ and the closest vertex
which follows the standard pattern of $P_{n}$ is at least $2$. By the
significant property of the standard pattern, $N$ cannot receive a signal from
broadcast vertices in the path. Therefore, $N$ receives a signal only once for
${\gamma}_{b}-$broadcast function $x^{\prime}_{0}$, $x^{\prime}_{0}$ is a
member of $B$.

However, $N$ in a new broadcast function cannot receive a signal from pendant
vertices. Therefore, $f(x_{0})-f(x^{\prime}_{0})=1$, which means that
$f(x^{\prime}_{0})<f(x_{0})$. This contradicts with the statement $(*)$, so we
can conclude that $A^{\prime}\neq\emptyset$ as desired. ∎

Consider the proof for Claim 3, we assume the algorithm, which transforms the
dominating broadcast function in the set $B$ to the dominating broadcast
function in the set $B$ with the lower value of $f$, as $\Phi$.

If $\Phi$ is used for some branch, it does not affect to other branches
because the power sent from that branch is still the same. Consider a branch
where its vertices cannot send a signal to its base vertex. Therefore, if
there are vertices on this branch such that they cannot receive a signal from
a base vertex, after being used the algorithm $\Phi$, these vertices still
cannot receive a signal from a base vertex. If there are vertices on this
branch such that they can receive a signal from a base vertex, after being
used the algorithm $\Phi$, these vertices still receive a signal from the same
base vertex. Also, after being used the the algorithm $\Phi$, each vertex on
this branch can still receive the same number of signals. We call those
invariance, $V$.

Figure 25: (above) The graph before being used the algorithm $\Phi$
(below) The graph after being used the algorithm $\Phi$ at the branch
containing the vertex $N$ (a blue vertex)

Consider the efficient broadcast $x$. The algorithm $\Phi$ is used to
transform $x$ for several times until the value of $f$ is $0$ to a new
dominating broadcast $x^{\prime}$. Thus, $x^{\prime}\in A^{\prime}$.

Consider a ${\gamma}_{b}-$broadcast function $x^{\prime}$. Assume that $S$ is
the set of base vertices that can send a signal. Let $|S|=t$ where $t$ is a
natural number less than or equal $m$. Thus, we can order vertices in set S in
clockwise order from $P_{1},P_{2},...,P_{t}$. For each $i\in\\{1,2,...,t\\}$,
let the signal strength of $P_{i}$ be $p_{i}$.

We provide two cases for the natural number $t$

Case $1$ $t>1$

Consider each $P_{i}$ as a figure shown. There are pendant vertices such that
those vertices do not receive a signal from $P_{i}$, but their base vertices
do. Assume that the set of these vertices are $T_{i}$. Therefore, from the
definition of $A^{\prime}$, those base vertices cannot receive a signal from
$P_{j}$ where $j\in\\{1,2,...,t\\}-\\{i\\}$. Thus, those pendant vertices
cannot receive a signal from any base vertices.

Figure 26: Disconnected paths (in ovals) after a broadcast vertex sends a
signal

Vertices in $T_{i}$ can be separated into several paths, corresponding to
their branches. Thus, every two vertices in $T_{i}$ which comes from different
branches cannot receive a signal from the same broadcast vertex. Otherwise,
their base vertices would receive the signal twice. We can conclude that those
several paths are independent to each other.

######  Claim 4.

$p_{i}<n$ for each $i\in\\{1,2,...,t\\}$

###### Proof.

We will prove this claim by the sake of contradiction. Assume that there is
$i_{0}\in\\{1,2,...,t\\}$ such that $p_{i_{0}}>n$. By the definition of
$A^{\prime}$, $P_{i_{0}}$ cannot send a signal to all base vertices because
there is another broadcast base vertex ($t>1$). Therefore, there is a branch
that $P_{i_{0}}$ cannot send a signal to any vertex on the branch. Also, all
vertices on the branch containing $P_{i_{0}}$ can receive the a signal from
$P_{i_{0}}$. Consider neighborhood branches $A,B$, the number of vertices,
which can receive a signal from $P_{i_{0}}$, of the branch $A$ differ at most
one from those of the branch $B$. By the idea of the Intermediate Value
Theorem, there is a branch $C$ such that only one vertex $T$ on the branch
cannot receive a signal from $P_{i_{0}}$. It is obvious that $T$ is the leaf
vertex on the branch $C$.

Figure 27: The existence of the point $T$ after $P_{i_{0}}$ sends a signal
with a strength $p_{i_{0}}$

Consider that the base vertex of the branch $C$ can receive a signal from
$P_{i_{0}}$. Therefore, this branch is the branch where its vertices cannot
send a signal to its base vertex. From the invariance $V$, $T$ cannot receive
a signal from a base vertex, and vertices on the branch $C$ except $T$ cannot
be broadcast vertices because they receive a signal from $P_{i_{0}}$. Also,
those vertices still receive a signal only once due to the property of the
efficient broadcast and the invariance $V$. Therefore, $T$ has to be a
broadcast vertex. However, this broadcast vertex can send a signal to the
neighbor vertex which interferes with the signal from $P_{i_{0}}$, which
contradicts with the fact that this vertex still receive a signal only once,
as desired. ∎

Lengths of those disconnected paths in a clockwise order can form a tuple
$(n,n-1,...,n-p_{i}+1,n-p_{i},n-p_{i}+1,...,n-1,n)$. Therefore, from the
standard pattern of ${\gamma}_{b}-$broadcast function, these disconnected
paths and vertices receiving a signal from $P_{i}$ use costs at least

$p_{i}+\lceil\frac{n-p_{i}}{3}\rceil+2(\lceil\frac{n-p_{i}+1}{3}\rceil+\lceil\frac{n-p_{i}+2}{3}\rceil+...+\lceil\frac{n}{3}\rceil)$

Next, we will find the relationship among $p_{1},p_{2},...,p_{t}.$ Each vertex
$P_{i}$ can send a signal to $2p_{i}+1$ vertices on the cycle, including
itself. From the definition of $A^{\prime}$, each vertex on the cycle can
receive only once from another vertex on the cycle or itself. Therefore,

$(2p_{1}+1)+(2p_{2}+2)+...+(2p_{k}+1)=m$ (1)

Thus, we can conclude that

$\gamma_{b}(S^{n}_{m})=min\bigg{(}$$\sum_{i=1}^{k}\Big{(}p_{i}+\lceil\frac{n-p_{i}}{3}\rceil+2(\lceil\frac{n-p_{i}+1}{3}\rceil+\lceil\frac{n-p_{i}+2}{3}\rceil+...+\lceil\frac{n}{3}\rceil)$$\Big{)}\bigg{)}$

Let
$F(p_{1},p_{2},...,p_{k})=\sum_{i=1}^{k}\Big{(}\lceil\frac{n-p_{i}}{3}\rceil+2(\lceil\frac{n-p_{i}+1}{3}\rceil+\lceil\frac{n-p_{i}+2}{3}\rceil+...+\lceil\frac{n}{3}\rceil)$),
for all positive number $a_{1},a_{2},...,a_{k},k$ such that
$(2p_{1}+1)+(2p_{2}+1)+...+(2p_{k}+1)=m$

Consider that
$\gamma_{b}(S^{n}_{m})=min(F(p_{1},p_{2},...,p_{k})+(p_{1}+p_{2}+...+p_{k}))=min(F(p_{1},p_{2},...,p_{k})+\frac{m-k}{2}).$
Therefore, it is sufficient to find the minimum value of function $F$

######  Claim 5.

If $p_{1}>p_{2}$, then $f(p_{1},p_{2},...,p_{k})\leq
f(p_{1}-1,p_{2}+1,p_{3},...,p_{k})$

###### Proof.

Consider that
$(2(p_{1}-1)+1)+(2(p_{2}+1)+1)+2p_{3}+...+2p_{k}=(2p_{1}+1)+(2p_{2}+1)+...+(2p_{k}+1)=m$,
which means that $(p_{1}-1,p_{2}+1,p_{3},...,p_{k})$ still follows the
condition $(1)$

$\displaystyle F(p_{1},p_{2},...)-F(p_{1}-1,p_{2}+1,...)$
$\displaystyle=\big{(}\lceil\frac{n-p_{1}}{3}\rceil+2\sum_{i=1}^{p_{1}}\lceil\frac{n-p_{1}+i}{3}\rceil+\lceil\frac{n-p_{2}}{3}\rceil$
$\displaystyle\quad+2\sum_{i=1}^{p_{2}}\lceil\frac{n-p_{2}+i}{3}\rceil\big{)}-\big{(}\lceil\frac{n-p_{1}+1}{3}\rceil$
$\displaystyle\quad+2\sum_{i=1}^{p_{1}-1}\lceil\frac{n-p_{1}+i+1}{3}\rceil+\lceil\frac{n-p_{2}-1}{3}\rceil$
$\displaystyle\quad+2\sum_{i=1}^{p_{2}+1}\lceil\frac{n-p_{2}+i-1}{3}\rceil\big{)}$
$\displaystyle=\big{(}\lceil\frac{n-p_{1}}{3}\rceil-\lceil\frac{n-p_{2}-1}{3}\rceil\big{)}$
$\displaystyle\quad+\big{(}\lceil\frac{n-p_{1}+1}{3}\rceil-\lceil\frac{n-p_{2}}{3}\rceil\big{)}$
$\displaystyle\leq 0\qquad(p_{1}\geq p_{2}+1)$

Therefore, $f(p_{1},p_{2},...,p_{k})\leq f(p_{1}-1,p_{2}+1,p_{3},...,p_{k})$
as desired. ∎

From Claim 5,

$f(1,p_{1}+p_{2}-1,p_{3},...,p_{n})\leq f(2,p_{1}+p_{2}-2,p_{3},...,p_{n})\leq
f(p_{1},p_{2},p_{3},...,p_{n})$

Thus, we can conclude that $f(1,p_{1}+p_{2}-1,p_{3},...,p_{n})\leq
f(p_{1},p_{2},p_{3},...,p_{n})$ if $p_{1}\geq p_{2}$. By obvious mathematical
induction, $f(p_{1},p_{2},p_{3},...,p_{n})\geq
f(\underbrace{1,1,...1}_{k-1\>1^{\prime}s},\frac{m-3k+2}{2})$, which means
that this function has a similar property with a convex function, the maximum
value appearing at the extremal element in the domain.

Therefore,

$\displaystyle\gamma_{b}(S^{n}_{m})$
$\displaystyle=min(f(\underbrace{1,1,...1}_{k-1\>1^{\prime}s},\frac{m-3k+2}{2})+(p_{1}+p_{2}+...+p_{k}))$
$\displaystyle=min(f(\underbrace{1,1,...1}_{k-1\>1^{\prime}s},\frac{m-3k+2}{2})+\frac{m-k}{2})$

Given that
$G(k)=f(\underbrace{1,1,...1}_{k-1\>1^{\prime}s},\frac{m-3k+2}{2})+\frac{m-k}{2}$
for all natural number $k$.

$\displaystyle
G(k)=(k-1)(\lceil\frac{n-1}{3}\rceil+2\lceil\frac{n}{3}\rceil)+\lceil\frac{n-x}{3}\rceil+2\sum_{i=1}^{x}\lceil\frac{n-x+i}{3}\rceil+\frac{m-k}{2}$

, where $x=\frac{m-3k+1}{2}$

######  Claim 6.

$G(k+2)\geq G(k)$ for each natural number $k$.

###### Proof.

Consider that

$\displaystyle
G(k+2)=(k+1)(\lceil\frac{n-1}{3}\rceil+2\lceil\frac{n}{3}\rceil)+\lceil\frac{n-x+3}{3}\rceil+2\sum_{i=1}^{x-3}\lceil\frac{n-x+i+3}{3}\rceil+\frac{m-k}{2}-1$

Therefore,

$\displaystyle G(k+2)-G(k)$
$\displaystyle=2(\lceil\frac{n-1}{3}\rceil+2\lceil\frac{n}{3}\rceil)-\lceil\frac{n-x}{3}\rceil-2\lceil\frac{n-x+1}{3}\rceil$
$\displaystyle\qquad-2\lceil\frac{n-x+2}{3}\rceil-\lceil\frac{n-x+3}{3}\rceil-1$
$\displaystyle=2(\lceil\frac{n-1}{3}\rceil-\lceil\frac{n-x+2}{3}\rceil)+(\lceil\frac{n}{3}\rceil-\lceil\frac{n-x}{3}\rceil)$
$\displaystyle\qquad+2(\lceil\frac{n}{3}\rceil-\lceil\frac{n-x+1}{3}\rceil)+(\lceil\frac{n}{3}\rceil-\lceil\frac{n-x+3}{3}\rceil-1)$
$\displaystyle\geq\lceil\frac{n}{3}\rceil-\lceil\frac{n-x}{3}\rceil-1\qquad(\text{That
is because $x\geq 3$})$

Because of $x\geq 3$,
$G(k+2)-G(k)\geq\lceil\frac{n}{3}\rceil-\lceil\frac{n-3}{3}\rceil-1=0$ as
desired.

∎

From Claim 6,

$\displaystyle G(1)\leq G(3)\leq G(5)\leq...$ $\displaystyle G(2)\leq G(4)\leq
G(6)\leq...$

As a result, the minimum value of the function $G$ is either $G(1)$ or $G(2)$.
$G(2)$ can be occurred if and only if $m$ is even and $m\geq 6$ (by $x>0$)

$\displaystyle G(2)$ $\displaystyle=f(1,\frac{m}{2}-2)$
$\displaystyle=(\lceil\frac{n-1}{3}\rceil+2\lceil\frac{n}{3}\rceil)+\lceil\frac{n-x}{3}\rceil+2\sum_{i=1}^{x}\lceil\frac{n-x+i}{3}\rceil+\frac{m-2}{2}$
$\displaystyle\geq(\lceil\frac{n-1}{3}\rceil+2\lceil\frac{n}{3}\rceil)+2\lceil\frac{n}{3}\rceil+\frac{m-2}{2}$
$\displaystyle\geq(\lceil\frac{n-1}{3}\rceil+2\lceil\frac{n}{3}\rceil)+\frac{m}{2}+1$
$\displaystyle>n+\frac{m}{2}$

However, $rad(S_{m}^{n})=n+\frac{m}{2}$, which means that
$rad(S_{m}^{n})<G(2).$ Thus, $G(2)$ cannot be the value of
$\gamma_{b}(S^{n}_{m})$. Therefore, this case cannot be the
$\gamma_{b}-$dominating broadcast function.

Case 2 $t=1$

From Case 1, the minimum value of the function $G$ is $G(1)$, which is the
condition of this case. There is only one broadcast base vertex, $P^{*}$,
being able to send a signal to cover every base vertices.

Let the signal strength of $P^{*}$ be $rad(S_{m}^{n})-k$. If $k$ is more than
$0$, there are $k$ vertices on the branch, $l^{*}$, opposite to $P^{*}$ that
cannot receive the signal from $P^{*}$. Also, there are $k-1$ vertices on each
branch which is neighbor with the branch $l^{*}$. Therefore, The total cost of
this broadcast function is

$\displaystyle
rad(S^{n}_{m})-k+\lceil\frac{k}{3}\rceil+\lceil\frac{k-1}{3}\rceil+\lceil\frac{k-1}{3}\rceil$
$\displaystyle\geq\gamma_{b}(S^{n}_{m})-k+\lceil\frac{k+(k-1)+(k-1)}{3}\rceil$
$\displaystyle=rad(S^{n}_{m})-k+\lceil\frac{3k-2}{3}\rceil$
$\displaystyle=rad(S^{n}_{m})-k+k$ $\displaystyle=rad(S^{n}_{m})$

Therefore, in the case of $k>0$, the $\gamma_{b}-$dominating function of
$S_{m}^{n}$ cannot be less than the radius of the sunlet graph. In the case of
$k=0$, the minimum cost of this function is also the radius of the sunlet
graph. Finally, we can conclude that

$\displaystyle\gamma_{b}(S^{n}_{m})=rad(S^{n}_{m})=n+\lfloor\frac{m}{2}\rfloor$

∎

Figure 28: The example of $\gamma_{b}-$ dominating broadcast function of
$S^{3}_{6}$ ($m$ is an even number) Figure 29: The example of $\gamma_{b}-$
dominating broadcast function of $S^{4}_{7}$ ($m$ is an odd number)

##  6 Discussion

In this paper, the $\gamma_{b}-$dominating broadcast function values for the
cycle graph and the $m-$Sunlet graph are evaluated. There is another variation
of the cycle and the Sunlet, called generalized Sunlet graph. The generalized
Sunlet graph is a cycle graph and straight paths extended from some vertices
of a cycle graph. However, lengths of paths are not necessarily the same,
which makes the proof more complicated. For our further work, we will evaluate
the $\gamma_{b}-$dominating broadcast function values of the generalized
Sunlet graph.

Figure 30: The example of the generalized Sunlet graph

## References

  * [1] R Anitha and RS Lekshmi.  N-sun decomposition of complete, complete bipartite and some harary graphs.  International Journal of Computational and Mathematical Sciences, 2(1):33–38, 2008.
  * [2] Jean E Dunbar, David J Erwin, Teresa W Haynes, Sandra M Hedetniemi, and Stephen T Hedetniemi.  Broadcasts in graphs.  Discrete Applied Mathematics, 154(1):59–75, 2006.
  * [3] David John Erwin.  Cost domination in graphs.  2001\.
  * [4] Teresa W Haynes, Stephen Hedetniemi, and Peter Slater.  Fundamentals of domination in graphs.  CRC Press, 1998.
  * [5] TW Haynes, ST Hedetniemi, and PJ Slater.  Domination in graphs: the theory, 1998.