RADIAL AND ANTIPODAL DOMINATION NUMBER OF TREES

RADIAL AND ANTIPODAL DOMINATION NUMBER OF TREES

R. Sivakumar, E. Shanmugam, D. Pandiaraja, KM. Kathiresan

[PDF]

Abstract

Motivated by the existing global domination parameter γg, in this paper we make the first move for the study of radial and antipodal domination numbers of a graph. A set S ⊆ V (G) is a radial (an andipodal) dominating set of a graph G if S is a dominating set of both G and R(G) (A(G)), where R(G) (A(G)) is the radial (andipodal) graph of G. The radial (antipodal) domination number γrad(G) (γdiam(G)) equals the minimum cardinality of a radial (an antipodal) dominating set of G. For any tree with radius atleast two, we have established the chain γ ≤ γg ≤ γrad < γdiam. For any tree T with rad(T) = 2, γrad=γ or γ + 1. If T is a tree of order n, then γdiam=γ + 1 if and only if T is either K1,n−1 or K ′ 1,n−1, where K ′ 1,n is a tree obtained from K1,n−1 by adding a new vertex to a pendent. We presented linear programming formulation to identify radial and antipodal dominating sets of a graph. Computational time studied was carried out on randomly generated graphs by use of MATLAB function. The computational time to find radial and antipodal domination was recorded as less than a second for those graphs with fewer than 100 nodes.

Keywords

global, radial, antipodal domination, LP formulation