Independent domination and vertex coloring in graphs

被引:0
作者
Arumugam, Subramanian [1 ,2 ]
Gupta, Purnima [2 ]
机构
[1] Ramco Inst Technol, Dept Comp Sci & Engn, Rajapalayam 626117, Tamil Nadu, India
[2] Univ Delhi, Ramanujan Coll, Dept Math, Delhi 110019, India
关键词
Independent domination number; independence number; chromatic number; split graphs; well-covered graphs;
D O I
10.1142/s1793830925500533; 10.1142/S1793830925500533
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G = (V,E) be a graph of order n. Let gamma(i)(G),beta(0)(G) and chi(G) denote respectively the independent domination number, independence number and chromatic number of G. These parameters satisfy the well known inequality gamma(i)(G) <= beta(0)(G) <= n - chi(G) + 1. In this paper we determine conditions under which the above inequalities become equalities and use these conditions to determine extremal graphs in some specific graph classes.
引用
收藏
页数:8
相关论文
共 6 条
[1]   DOMINATION AND INDEPENDENT DOMINATION NUMBERS OF A GRAPH [J].
ALLAN, RB ;
LASKAR, R .
DISCRETE MATHEMATICS, 1978, 23 (02) :73-76
[2]  
Chartrand G., 2000, GRAPHS DIGRAPHS
[3]  
Chartrand G, 2009, CRC DISCR MATH APPL, P1
[4]   Graphs with equal domination and independent domination numbers [J].
Gupta, Purnima ;
Singh, Rajesh ;
Arumugam, S. .
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (02) :691-696
[5]  
Haynes T.W., 1998, FUNDAMENTALS DOMINAT
[6]   ON GRAPHS WITH EQUAL DOMINATION AND INDEPENDENT DOMINATION NUMBERS [J].
TOPP, J ;
VOLKMANN, L .
DISCRETE MATHEMATICS, 1991, 96 (01) :75-80