摘要
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.
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.
基金
Supported by NNSF of China(11101383,61373106)
