| A Linear-Time Algorithm for 2-Step Domination in Block Graphs |
| Received:April 19, 2014 Revised:January 16, 2015 |
| Key Words:
2-step domination block graph algorithm labeling method
|
| Fund Project:Supported by the National Natural Science Foundation of China (Grant No.11271365) and the Domestic Senior Visiting Scholar Program in Higher Occupation Colleges in Jiangsu Province (Grant No.2014FX075). |
| Author Name | Affiliation | | Yancai ZHAO | School of Science, Jiangnan University, Jiangsu 214122, P. R. China
Wuxi City College of Vocational Technology, Jiangsu 214153, P. R. China | | Lianying MIAO | Department of Mathematics, China University of Mining and Technology, Jiangsu 221116, P. R. China | | Zuhua LIAO | School of Science, Jiangnan University, Jiangsu 214122, P. R. China |
|
| Hits: 2937 |
| Download times: 2987 |
| Abstract: |
| The 2-step domination problem is to find a minimum vertex set $D$ of a graph such that every vertex of the graph is either in $D$ or at distance two from some vertex of $D$. In the present paper, by using a labeling method, we provide an $O(m)$ time algorithm to solve the 2-step domination problem on block graphs, a superclass of trees. |
| Citation: |
| DOI:10.3770/j.issn:2095-2651.2015.03.006 |
| View Full Text View/Add Comment |
