Maximal independent sets in complementary prism graphs

被引:0
作者
Barbosa, Rommel M. [1 ]
Cappelle, Marcia R. [1 ]
Coelho, Erika M. M. [1 ]
机构
[1] Univ Fed Goias, Inst Informat, Goiania, Go, Brazil
关键词
Well-covered graph; maximal independent set; DOMINATION;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph and (G) over bar be the complement of G. The complementary prism of G, denoted by G (G) over bar, is the graph formed by the disjoint union of G and (G) over bar by adding the edges of a perfect matching between the corresponding vertices of G and (G) over bar. A graph G is well-covered if every maximal independent set of G has the same cardinality. We prove that if G (G) over bar is well-covered and G is not well covered, G has exactly two consecutive sizes of maximal independent sets. We prove other results concerning well-covered complementary prisms.
引用
收藏
页码:283 / 294
页数:12
相关论文
共 11 条
[1]   Recognizing some complementary products [J].
Cappelle, Marcia R. ;
Penso, Lucia ;
Rautenbach, Dieter .
THEORETICAL COMPUTER SCIENCE, 2014, 521 :1-7
[2]  
Desormeaux WJ, 2013, UTILITAS MATHEMATICA, V91, P131
[3]  
Desormeaux WJ, 2011, UTILITAS MATHEMATICA, V86, P267
[4]  
Duarte M. A., REMARKS COMPLE UNPUB
[5]  
Góngora JA, 2013, UTILITAS MATHEMATICA, V91, P3
[6]  
Haynes T., 2009, C NUMER, V199, P45
[7]  
Haynes T.W., 2007, Bull. Inst. Comb. Appl., V51, P21
[8]   Domination and total domination in complementary prisms [J].
Haynes, Teresa W. ;
Henning, Michael A. ;
van der Merwe, Lucas C. .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (01) :23-37
[9]  
Holmes K.R.S., 2010, J COMBIN MATH COMBIN, V72, P163
[10]  
Kazemi A.P., 2011, ISRN DISCRETE MATH