Independent point-set dominating sets in graphs

被引:1
作者
Gupta, Purnima [1 ]
Goyal, Alka [2 ]
Jain, Ranjana [2 ]
机构
[1] Univ Delhi, Dept Math, Sri Venkateswara Coll, Delhi 110021, India
[2] Univ Delhi, Dept Math, Delhi 110007, India
关键词
Domination; Point-set domination; Independent set; Equivalence relation; Duplicated equivalent;
D O I
10.1016/j.akcej.2019.08.001
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper, we study graphs which possess an independent point-set dominating set (in short, ipsd-set). We call such a graph as an ipsd-graph. We first provide general structural characterization of separable ipsd-graphs and thereafter, in our quest to characterize such graphs, we establish that girth of an ipsd-graph is at most 5. We further characterize ipsd-graphs with girth 5 and C5-free ipsd-graphs of girth 4. Then, we exhibit a class of ipsd-graphs with girth g(G)=4 containing C5 as an induced subgraph and in the process, we introduce a new graph equivalence relation termed as duplicated equivalence.
引用
收藏
页码:229 / 241
页数:13
相关论文
共 18 条
[1]  
Acharya B.D., 1997, Journal of Combinatorics, Information and System Sciences, V22, P133
[2]   On point-set domination in graphs IV: Separable graphs with unique minimum psd-sets [J].
Acharya, BD ;
Gupta, P .
DISCRETE MATHEMATICS, 1999, 195 (1-3) :1-13
[3]  
Acharya BD, 2000, NATL ACAD SCI LETT, V23, P171
[4]  
Berge C., 1973, Graphs and Hypergraphs
[5]   THE INDEPENDENCE RATIO OF REGULAR GRAPHS [J].
BOLLOBAS, B .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1981, 83 (02) :433-436
[6]  
Bujurke N.M., 1996, PROC NAT S RECENT TR
[7]  
Chartrand G., 2005, GRAPHS DIGRAPHS, V4th
[8]  
Gupta P., 2016, Electronic Notes in Discrete Mathematics, V53, P213
[9]   Characterizing minimal point set dominating sets [J].
Gupta, Purnima ;
Singh, Rajesh ;
Arumugam, S. .
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2016, 13 (03) :283-289
[10]  
Gupta Purnima., 2017, LECT NOTES COMPUT SC, V10398, P300