On average lower independence and domination numbers in graphs

详细信息    查看全文

• 作者：Blidia ; Mostafa ; Chellali ; Mustapha ; Maffray ; Fr??d??ric
• 关键词：05C69 ; Average lower independence number ; Average lower domination number ; Extremal graph
• 刊名：Discrete Mathematics
• 出版年：2005
• 出版时间：May 28, 2005
• 年：2005
• 卷：295
• 期：1-3
• 页码：1-11
• 全文大小：213 K

文摘

The average lower independence number i_av(G) of a graph G=(V,E) is defined as , and the average lower domination number γ_av(G) is defined as , where i_v(G) (resp. γ_v(G)) is the minimum cardinality of a maximal independent set (resp. dominating set) that contains v. We give an upper bound of i_av(G) and γ_av(G) for arbitrary graphs. Then we characterize the graphs achieving this upper bound for i_av and for γ_av respectively.