Fair Domination in Graphs

Details Fair Domination in Graphs Fair Domination in Graphs

2011-09-06

arxiv.org/abs/1109.1150v1

Mathematics

Combinatorics

18 pages

Scientific paper

A fair dominating set in a graph $G$ (or FD-set) is a dominating set $S$ such that all vertices not in $S$ are dominated by the same number of vertices from $S$; that is, every two vertices not in $S$ have the same number of neighbors in $S$. The fair domination number, $fd(G)$, of $G$ is the minimum cardinality of a FD-set. We present various results on the fair domination number of a graph. In particular, we show that if $G$ is a connected graph of order $n \ge 3$ with no isolated vertex, then $fd(G) \le n - 2$, and we construct an infinite family of connected graphs achieving equality in this bound. We show that if $G$ is a maximal outerplanar graph, then $fd(G) < 17n/19$. If $T$ is a tree of order $n \ge 2$, then we prove that $fd(T) \le n/2$ with equality if and only if $T$ is the corona of a tree.

Affiliated with

Also associated with

No associations

Rating

Fair Domination in Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fair Domination in Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair Domination in Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-93423