Minimum Dominating Tree Problem for Graphs

LIN Hao, LIN Lan

doi:10.13371/j.cnki.chin.q.j.m.2014.01.001

Chinese Quarterly Journal of Mathematics >

2014 , Vol. 29 >Issue 1: 1 - 8

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2014.01.001

Minimum Dominating Tree Problem for Graphs

Expand

1. School of Science, Henan University of Technology 2. School of Electronics and Information Engineering, Tongji University

LIN Hao (1974-), male, native of Taishan, Guangdong, an associate professor of Henan University of Technology, M.S.D., engages in network optimization.

Received date: 2013-03-01

Online published: 2022-11-28

Supported by

Supported by NNSF of China (11101383,61373106)

Fold

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

Cite this article

LIN Hao, LIN Lan .

Minimum Dominating Tree Problem for Graphs

[J]. Chinese Quarterly Journal of Mathematics, 2014 , 29(1) : 1 -8 . DOI: 10.13371/j.cnki.chin.q.j.m.2014.01.001

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article