Article ID Journal Published Year Pages File Type
9513400 Discrete Mathematics 2005 11 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,