Advances and Applications in Discrete Mathematics
Volume 26, Issue 1, Pages 17 - 33
(January 2021) http://dx.doi.org/10.17654/DM026010017 |
|
SIGNED STAR DOMINATION IN GRAPHS
Yancai Zhao and Zuosong Liang
|
Abstract: For a graph without isolated vertex, a function is said to be a signed star dominating function of G if for every where The minimum value of taken over all signed star dominating functions f of G, is called the signed star domination number of G. In this paper, we provide a new upper bound for the signed star domination number of a general graph, in terms of the matching number of the graph, compute the exact values of signed star domination number of some regular graphs, and construct a graph H from any given graph G such that the edge covering number of H is equal to the signed star domination number of G. Finally, we present a linear time algorithm to compute the signed star domination number of cacti, a super class of trees. For this purpose, a series of configurations in a cactus should be dealt with. |
Keywords and phrases: signed star domination, cactus, graph configuration, algorithm.
|
|
Number of Downloads: 193 | Number of Views: 491 |
|