Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9513400 | Discrete Mathematics | 2005 | 11 Pages |
Abstract
The average lower independence number iav(G) of a graph G=(V,E) is defined as 1|V|âvâViv(G), and the average lower domination number γav(G) is defined as 1|V|âvâVγv(G), where iv(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 iav(G) and γav(G) for arbitrary graphs. Then we characterize the graphs achieving this upper bound for iav and for γav respectively.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Mostafa Blidia, Mustapha Chellali, Frédéric Maffray,