Chinese Quarterly Journal of Mathematics ›› 2014, Vol. 29 ›› Issue (1): 1-8.doi: 10.13371/j.cnki.chin.q.j.m.2014.01.001

    Next Articles

Minimum Dominating Tree Problem for Graphs

  

  1. 1. School of Science, Henan University of Technology 2. School of Electronics and Information Engineering, Tongji University
  • Received:2013-03-01 Online:2014-03-30 Published:2022-11-28
  • About author:LIN Hao (1974-), male, native of Taishan, Guangdong, an associate professor of Henan University of Technology, M.S.D., engages in network optimization.
  • Supported by:
    Supported by NNSF of China (11101383,61373106)

Abstract: A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.

Key words: network optimization, minimum dominating tree, special graphs, exact evaluation

CLC Number: