---
abstract: |
    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, ${{\rm 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 ${{\rm 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 ${{\rm fd}}(G) < 17n/19$. If $T$ is a tree of order $n \ge 2$, then we prove that ${{\rm fd}}(T) \le n/2$ with equality if and only if $T$ is the corona of a tree.
---

[Fair Domination in Graphs]{}\

[2]{}

Yair Caro\
[Dept. of Mathematics and Physics\
University of Haifa-Oranim\
Tivon 36006, Israel\
yacaro@kvgeva.org.il]{}

Adriana Hansberg\
[Dept. de Matemàtica Aplicada III\
UPC Barcelona\
08034 Barcelona, Spain\
adriana.hansberg@upc.edu]{}\

Michael Henning\
[Dept. of Mathematics\
University of Johannesburg\
Auckland Park 2006, South Africa\
mahenning@uj.ac.za]{}

\

[**Keywords:** Fair domination. ]{}\

Introduction
============

In this paper, we continue the study of domination in graphs. Domination in graphs is now well studied in Graph Theory. The literature on this subject has been surveyed and detailed in the two books by Haynes, Hedetniemi, and Slater [@hhs1; @hhs2]. For notation and Graph Theory terminology we in general follow [@hhs1]. Specifically, let $G = (V, E)$ be a graph with vertex set $V$ of order $n = |V|$ and edge set $E$ of size $m =
|E|$, and let $v$ be a vertex in $V$. The *open neighborhood* of $v$ is the set $N(v) = \{u \in V \, | \, uv \in E\}$, while the *closed neighborhood* of $v$ is the set $N[v] = N(v) \cup
\{v\}$.

Let $G = (V,E)$ be a graph. A *dominating set* in $G$ is a set $D$ of vertices of $G$ such that every vertex $v \in V$ is either in $D$ or adjacent to a vertex of $D$. A vertex in $D$ is said to *dominate* a vertex outside $D$ if they are adjacent in $G$. The *domination number* of $G$, denoted $\gamma(G)$, is the minimum cardinality of a dominating set. A dominating set of $G$ of cardinality $\gamma(G)$ is called a $\gamma(G)$-set.

Let $G$ be a graph that is not the empty graph. For $k \ge 1$ an integer, a *$k$-fair dominating set*, abbreviated kFD-set, in $G$ is a dominating set $D$ such that $|N(v) \cap D| = k$ for every vertex $v \in V \setminus D$. We note that the set $D = V$ is a kFD-set since vacuously every vertex in $V \setminus D = \emptyset$ satisfies the desired property. The *$k$-fair domination number* of $G$, denoted by ${{\rm fd}_k}(G)$, is the minimum cardinality of a kFD-set. A kFD-set of $G$ of cardinality ${{\rm fd}_k}(G)$ is called a ${{\rm fd}_k}(G)$-set. With this definition in mind, we point to a related problem on the so called $(k, \tau)$-regular sets discussed in [@CKV] (and all the references given there). Some reminiscent of this approach appears more explicitly in Proposition \[l:line1\].

A *fair dominating set*, abbreviated FD-set, in $G$ is a kFD-set for some integer $k \ge 1$. Thus a dominating set $D$ is a FD-set in $G$ if $D = V$ or if $D \ne V$ and all vertices not in $D$ are dominated by the same number of vertices from $D$; that is, $|N(u)
\cap D| = |N(v) \cap D| > 0$ for every two vertices $u, v \in V
\setminus D$. We remark that if $G \ne {{\overline{K}}}_n$, then $G$ contains a vertex $v$ that is not isolated in $G$ and the set $V \setminus \{v\}$ is a FD-set in $G$. Hence every graph that is not empty has a FD-set of cardinality strictly less than its order. The *fair domination number*, denoted by ${{\rm fd}}(G)$, of a graph $G$ that is not the empty graph is the minimum cardinality of a FD-set in $G$. By convention, if $G = {{\overline{K}}}_n$, we define ${{\rm fd}}(G) =
n$. Hence if $G$ is not the empty graph, then ${{\rm fd}}(G) = \min \{
{{\rm fd}_k}(G) \}$, where the minimum is taken over all integers $k$ where $1 \le k \le |V|-1$. A FD-set of $G$ of cardinality ${{\rm fd}}(G)$ is called a ${{\rm fd}}(G)$-set. Every FD-set in a graph $G$ is a dominating set in $G$. Hence we have the following observation.

Let $G$ be a graph of order $n$. Then the following holds.\
$\gamma(G) \le {{\rm fd}}(G)$.\
${{\rm fd}}(G) \le n$, with equality if and only if $G =
{{\overline{K}}}_n$. \[ob1\]

We show later (see Corollary \[c:bound\]) that the result in Observation \[ob1\](b) can be improved as follows: if $G$ is a graph of order $n$, then ${{\rm fd}}(G) \le n-2$, unless $G = {{\overline{K}}}_n$, in which case ${{\rm fd}}(G) = n$, or $G$ contains precisely one edge, in which case ${{\rm fd}}(G) = n-1$.

For example, consider the Petersen graph $G = G_{10}$ shown in Figure \[Peter\] which has domination number $\gamma(G) = 3$. Let $V = V(G)$. The only possible $\gamma(G)$-sets are the open neighborhoods $D = N(v)$, where $v \in V$, but these are not FD-sets since if $u \in V \setminus D$, then either $u \ne v$, in which case $|N(u) \cap D| = 1$, or $u = v$, in which case $|N(u) \cap D| = 3$. Thus, by Observation \[ob1\](a), ${{\rm fd}}(G) > \gamma(G) = 3$. However the closed neighborhood $N[v]$ of any vertex $v \in V$ forms a FD-set in $G$, and so ${{\rm fd}}(G) \le |N[v]| = 4$. Consequently, ${{\rm fd}}(G) = 4$.

=\[circle, draw, fill=black!0, inner sep=0pt,minimum width=.2cm\]

(0,0) [ +(1.90,3.62) – +(0.00,2.24) +(0.00,2.24) – +(0.73,0.00) +(0.73,0.00) – +(3.08,0.00) +(3.08,0.00) – +(3.80,2.24) +(1.90,3.62) – +(3.80,2.24) +(1.90,3.62) – +(1.90,2.62) +(0.00,2.24) – +(0.95,1.93) +(1.31,0.81) – +(0.73,0.00) +(2.49,0.81) – +(3.08,0.00) +(2.85,1.93) – +(3.80,2.24) +(1.90,2.62) – +(2.49,0.81) +(2.49,0.81) – +(0.95,1.93) +(0.95,1.93) – +(2.85,1.93) +(2.85,1.93) – +(1.31,0.81) +(1.31,0.81) – +(1.90,2.62) +(0.95,1.93) node +(0.00,2.24) node +(1.90,2.62) node +(1.90,3.62) node +(2.85,1.93) node +(2.49,0.81) node +(1.31,0.81) node +(0.73,0.00) node +(3.08,0.00) node +(3.80,2.24) node ]{};

-0.6 cm

An *out-regular set*, abbreviated OR-set, of a graph $G$ that is not the empty graph is a set $Q$ of vertices such that $|N(u) \cap (
V \setminus Q )| = |N(v) \cap ( V \setminus Q)| > 0$ for every two vertices $u$ and $v$ in $Q$. We remark that if $G \ne {{\overline{K}}}_n$, then $G$ contains a vertex $v$ that is not isolated in $G$ and the set $\{v\}$ is an OR-set in $G$. Hence every graph that is not empty has an OR-set. The *out-regular number* of a non-empty graph $G$, denoted by ${\xi_{\rm or}}(G)$, is the maximum cardinality of an OR-set. By convention, if $G = {{\overline{K}}}_n$, we define ${\xi_{\rm or}}(G) = 0$. An OR-set of $G$ of cardinality ${\xi_{\rm or}}(G)$ is called an ${\xi_{\rm or}}(G)$-set. Since every graph that is not empty has an OR-set, we have the following observation.

Let $G$ be a graph of order $n$. Then, ${\xi_{\rm or}}(G) \ge 0$, with equality if and only if $G = {{\overline{K}}}_n$. \[ob2\]

If $S$ is a packing in $G$ (and so, the vertices in $S$ are pairwise at distance at least $3$ apart in $G$), then in order to dominate the vertices in $S$ every dominating set in $G$ must contain at least one vertex in $N[v]$ for each $v \in S$, and so $\gamma(G) \ge |S|$. A *perfect dominating set*, abbreviated PD-set, in $G$ is a dominating set $S$ that is a packing in $G$. Thus if $S$ is a PD-set in $G$, then every vertex not in $S$ is dominated by a unique vertex in $S$, and so $S$ is a 1FD-set, implying that ${{\rm fd}}(G) \le {{\rm fd}_1}(G)
\le \gamma(G)$. Consequently, by Observation \[ob1\], we have the following observation.

If a graph $G$ has a PD-set, then $\gamma(G) = {{\rm fd}_1}(G)  = {{\rm fd}}(G)$. \[ob3\]

Notation
--------

We denote the *degree* of $v$ in $G$ by $d_G(v)$, or simply by $d(v)$ if the graph $G$ is clear from context. Let $\delta(G)$, $\Delta(G)$ and ${{\overline{d}}}(G)$ denote, respectively, the minimum degree, the maximum degree and the average degree in $G$. For a set $S\subseteq V$, we denote the number of vertices of $S$ adjacent to $v$ in $G$ by $d_S(v)$. In particular, $d_V(v) = d_G(v)$. For a set $S \subseteq V$, the subgraph induced by $S$ is denoted by $G[S]$. We denote by ${{\rm span}}(G)$, the *span* of $G$, the number of distinct values in the degree sequence of $G$ and by ${{\rm rep}}(G)$, the *repetition number* of $G$, the maximum multiplicity in the list of vertex degrees. The parameter $\alpha(G)$ denotes the (vertex) *independence number* of $G$, while $\chi(G)$ denotes the *chromatic number* of $G$.

Further, we denote the complete graph on $n$ vertices by $K_n$ and the empty graph on $n$ vertices by ${{\overline{K}}}_n$. Moreover, $P_n$, $C_n$ and $K_{m,n}$ denote, respectively, the path on $n$ vertices, the cycle on $n$ vertices and the complete bipartite graph with one partite set of cardinality $m$ and the other of cardinality $n$.

Preliminary Results and Observations
====================================

It is a simple exercise to determine the fair domination number of certain well-studied families of graphs. Recall that for $n \ge 3$, $\gamma(P_n) = \gamma(C_n) = \lceil n/3 \rceil$, while for $m \ge n
\ge 2$, $\gamma(K_{m,n}) = 2$.

\[ob4\] For $m, n \ge 1$, if $G \in \{P_n,K_n,{{\overline{K}}}_n,K_{m,n}\}$, then ${{\rm fd}}(G) = \gamma(G)$. Further for $n \ge 3$, ${{\rm fd}}(C_n) = \gamma(C_n)$ unless $n \equiv 2 \, ({{\rm mod}}\, 3)$ and $n \ge 5$ in which case ${{\rm fd}}(C_n) = \gamma(C_n) + 1$.

We next establish a relationship between the fair domination number and the out-regular number of a graph.

For every graph $G$ of order $n \ge 2$, ${{\rm fd}}(G) + {\xi_{\rm or}}(G) = n$. \[prop1\]

**Proof.** If $G = {{\overline{K}}}_n$, then ${{\rm fd}}(G) = n$ and, by convention, ${\xi_{\rm or}}(G) = 0$. Hence we may assume that $G \ne {{\overline{K}}}_n$, for otherwise the desired result holds. Let $D$ be a ${{\rm fd}}(G)$-set. By Observation \[ob1\](b), ${{\rm fd}}(G) < n$. Let $Q = V \setminus D$. Then, $Q$ is an OR-set in $G$, and so ${\xi_{\rm or}}(G) \ge |Q| = n -
{{\rm fd}}(G)$, or, equivalently, ${{\rm fd}}(G) + {\xi_{\rm or}}(G) \ge n$. Conversely, let $Q$ be an ${\xi_{\rm or}}(G)$-set. By Observation \[ob2\], ${\xi_{\rm or}}(G)
> 0$. By definition, ${\xi_{\rm or}}(G) < n$. Let $D = V \setminus Q$. Then, $D$ is a FD-set, and so ${{\rm fd}}(G) \le |D| = n - {\xi_{\rm or}}(G)$, or, equivalently, ${{\rm fd}}(G) + {\xi_{\rm or}}(G) \le n$. Consequently, ${{\rm fd}}(G) +
{\xi_{\rm or}}(G) = n$. [$\Box$]{}

Let G be a connected graph on $n \ge 2$ vertices. Then the following holds.\
If ${\overline{G}}$ is connected, then ${{\rm fd}}(G) =
{{\rm fd}}({\overline{G}})$.\
If ${\overline{G}}$ has $q \ge 2$ components, then ${{\rm fd}}(G)
\le n/q \le n/2$. \[thm:Gbar\]

**Proof.** (a) Suppose that ${\overline{G}}$ is connected. Let $D$ be a ${{\rm fd}}(G)$-set. Then every vertex $v \in V \setminus D$ is adjacent to precisely $k$ vertices in $D$ for some integer $k$, $1 \le k \le
|D|$. If $k = |D|$, then in ${\overline{G}}$ there are no edges between $D$ and $V \setminus D$, contradicting the assumption that ${\overline{G}}$ is connected. Hence, $k < |D|$. But then in ${\overline{G}}$ every vertex in $V
\setminus D$ is adjacent to precisely $|D| - k > 0$ vertices in $D$, and so $D$ is a FD-set in ${\overline{G}}$. Thus, ${{\rm fd}}({\overline{G}}) \le |D| =
{{\rm fd}}(G)$. Reversing the roles of $G$ and ${\overline{G}}$, we have that ${{\rm fd}}(G)
\le {{\rm fd}}({\overline{G}})$. Consequently, ${{\rm fd}}(G) = {{\rm fd}}({\overline{G}})$.

\(b) Suppose that ${\overline{G}}$ is not connected and has $q$ components. Clearly, the smallest component in ${\overline{G}}$ has cardinality at most $n/q$. Let $F$ be the smallest component in ${\overline{G}}$ and let $D = V(F)$. Then in $G$ every vertex in $V \setminus
D$ is adjacent to all vertices in $D$, and so $D$ is a FD-set in $G$. Thus, ${{\rm fd}}(G) \le |D| \le n/q \le n/2$. [$\Box$]{}

Next we consider the fair domination number of the line graph, $L(G)$, of a graph $G$.

Let $G$ be a graph of size $\mG$ and let $L(G)$ denote the line graph of $G$. If $H$ is a spanning $r$-regular subgraph of $G$, where $r
> 0$ and where $H$ is not necessarily induced, of size $\mH$, then $${{\rm fd}}(L(G)) \le \mH = \left( \frac{\mH}{\mG} \right) |V(L(G)))|.$$ \[l:line1\]

**Proof.** Let $D$ be the set of vertices in the line graph $L(G)$ of $G$ corresponding to the edges in $H$, and let $v \in
V(L(G)) \setminus D$. Thus the vertex $v$ corresponds to an edge $e
\in E(G) \setminus E(H)$, and so both ends of $e$ are incident with precisely $r$ edges of $H$. Hence in $L(G)$, the vertex $v$ is adjacent to exactly $2r$ vertices in $D$. Thus in $L(G)$, we have that $|N(v) \cap D| = 2r$ for every vertex $v \in V(L(G)) \setminus
D$, implying that $D$ is a FD-set in $L(G)$, and so ${{\rm fd}}(L(G)) \le
|D| = \mH$. [$\Box$]{}

We remark that examples of graphs that possess spanning $r$-regular subgraphs, where $r > 0$ and where $H$ is not necessarily induced, are abundant. For example, regular graphs of even degree have a $2$-factor as do Hamiltonian graphs. Several interesting families of graphs possess a $1$-factor (or perfect matching), including regular bipartite graphs and connected claw-free graphs of even order. For further results about regular spanning graphs see for example [@Cs07; @HoVo].

Results
=======

Upper Bounds
------------

We first establish upper bounds on the fair domination of a graph in terms of its order. By Observation \[ob3\](a), ${{\rm fd}}(G) \le n$ with equality if $G = {{\overline{K}}}_n$. However this bound can be improved slightly if we restrict our attention to graphs without isolated vertices.

If $G$ is a graph of order $n \ge 3$ with $\delta(G) \ge 1$, then ${{\rm fd}}(G) \le n - 2$, and this bound is sharp. \[thm\_n2\]

**Proof.** We proceed by induction on $n \ge 3$. If $n \in
\{3,4\}$, it is a simple case to check that if $G$ is a graph of order $n$ with no isolated vertex, then ${{\rm fd}}(G) \le n - 2$. This establishes the base cases. Let $n \ge 5$ and assume that every graph $G'$ of order $n'$, where $3 \le n' < n$, with no isolated vertex satisfies ${{\rm fd}}(G') \le n' - 2$. Let $G = (V,E)$ be a graph of order $n$ with no isolated vertex. Every graph on at least two vertices has two vertices of the same degree. Let $u$ and $v$ be two vertices in $G$ with the same degree. Then, $d_G(u) = d_G(v) = k$ for some $k$, where $1 \le k \le n-1$. If $u$ and $v$ are not adjacent in $G$ or if $u$ and $v$ are adjacent in $G$ and $k \ge 2$, then $D = V
\setminus \{u,v\}$ is a FD-set, and so ${{\rm fd}}(G) \le |D| = n - 2$, as desired. Hence we may assume that $u$ and $v$ are adjacent in $G$ and $k = 1$. We now consider the graph $G' = G - \{u,v\}$ of order $n' =
n - 2 \ge 3$. Since $G$ has no isolated vertex, neither does $G'$. Applying the inductive hypothesis to $G'$, we have that ${{\rm fd}}(G') \le
n' - 2$. Every ${{\rm fd}}(G')$-set can be extended to a FD-set in $G$ by adding to it the vertices $u$ and $v$, implying that ${{\rm fd}}(G) \le
{{\rm fd}}(G') + 2 \le n' = n-2$. This establishes the desired upper bound.

We show next that the upper bound is sharp. For this purpose we construct an infinite family of graphs $G$ of order $n \ge 3$ with $\delta(G) \ge 1$ satisfying ${{\rm fd}}(G) = n - 2$. We consider two cases in turn, depending on the parity of $n$.

[Claim I.]{} There exists an infinite family of graphs $H$ of even order $\nH$ satisfying ${{\rm fd}}(H) = \nH - 2$.

**Proof.** For $n \ge 3$ define the graph $H = H_n$ on $\nH =
2n$ vertices as follows: Let $V(H) = X \cup Y$, where $X =
\{x_1,\ldots,x_n\}$ and $Y = \{y_1,\ldots,y_n\}$, and where $x_i$ is adjacent to $y_j$ if and only if $i \ge j$. Further $Y$ is an independent set and, for $i,j > 1$, $x_i$ is adjacent to $x_j$. Thus, $d_H(x_1)  = 1$ and $d_H(x_i) = i +
n - 2$ for $1 < i \le n$, while $d_H(y_i)  = n- i +1$ for $1 \le i
\le n$. We note that $d_H(x_1) = d_H(y_n) = 1$ and $d_H(y_1) =
d_H(x_2) = n$ and the degrees of all other vertices in $H$ are distinct. We show that ${{\rm fd}}(H) = 2n-2 = \nH - 2$. Let $S$ be an arbitrary FD-set of $H$. We show that $|S| \ge \nH-2$. We consider three cases in turn.

*Case I.1. $x_1 \notin S$*. Then evidently $y_1 \in S$ and $S$ is a 1FD-set of $H_n$. If $x_i \notin S$ for some $i \ge 2$, then $N(x_i) \cap S = \{y_1\}$ and thus $y_2 \notin S$. Since $y_2$ has to be dominated by $S$, there is some $l \ge 2$, $l \neq i$, such that $x_l \in S$, implying that $y_1, x_l \in N(x_i) \cap S$, a contradiction. Hence, $X \setminus \{x_1\} \subseteq S$. Moreover, $y_j \in S$ for any $1 < j < n$, since $|N(y_j) \cap S| \ge |N(y_j)
\cap (X \setminus \{x_1\})| = n-j+1 \ge 2$ and $S$ is a 1FD-set. Thus $V \setminus \{x_1, y_n\} \subseteq S$ and $|S| \ge \nH-2$, so we are done.

*Case I.2. $x_1 \in S$ and $y_n \notin S$.* Then evidently $x_n \in S$ and $S$ is a 1FD-set of $H_n$. Since $x_1, x_n
\in N(y_1) \cap S$, it follows that $y_1 \in S$. Hence, as $x_n, y_1
\in N(x_i) \cap S$ for any $1< i < n$, we have that $X \subseteq S$. This implies also that $y_j \in S$ for any $1 <j < n$ and thus $V
\setminus \{y_n\} \subseteq S$ and therefore $|S| \ge \nH-1$.

*Case I.3. $x_1, y_n \in S$.* We divide this case in three parts.

*(i) Suppose that $y_1 \notin S$.* Then $y_j \in S$ for every $1 < j < n$, otherwise $|N(y_1) \cap S| > |N(y_j) \cap S|$ since $N(y_j) \subset N(y_1)$ and $x_1 \in N(y_1) \setminus N(y_j)$. As $N(x_i) \varsubsetneqq N(x_{i+1})$ for all $1 < i < n-1$, it follows that there is at most one index $1 < i < n$ such that $x_i
\notin S$, implying that $|S| \ge \nH-2$.

*(ii) Suppose that $y_1 \in S$ and $x_n \notin S$.* Then as $N(x_i) \subset N(x_n)$ and $y_n \in S \cap (N(x_n) \setminus
N(x_i))$ for each $1 < i < n$, it follows that $X \setminus \{x_n\}
\subset S$. Hence, as every $y_j$ has a different number of neighbors in $X \setminus \{x_n\}$, $y_j \in S$ for all $1 < j < n$. Hence $|S|
\ge \nH-1$.

*(iii) Suppose that $y_1 \in S$ and $x_m \in S$.* If $x_i \notin S$ for some $1 < i < m$, then $y_j \in S$ for every $1 <
j < m$, since $N(y_j) \subset N(x_i)$ and $y_1 \in S \cap (N(x_i)
\setminus N(y_j))$. Then $X \setminus \{x_i\} \subset S$ and thus $|S| \ge \nH-1$ and we are done. Thus assume that $X \subset S$. Then $|Y \cap S| \ge n-1$, otherwise two different vertices from $Y$ would not be fairly dominated by $S$. Hence again $|S| \ge \nH-1$.

In all three cases, we have that $|S| \ge \nH-2$. Since $S$ is an arbitrary FD-set of $H$, it follows that ${{\rm fd}}(H) \ge \nH - 2$. However as shown earlier, ${{\rm fd}}(H) \le \nH - 2$. Consequently, ${{\rm fd}}(H) = \nH -
2$. This completes the proof of Claim I. [[($\Box$)]{}]{}

[Claim II.]{} There exists an infinite family of graphs $F$ of odd order $\nF$ satisfying ${{\rm fd}}(F) = \nF - 2$.

**Proof.** For $n \ge 3$ define the graph $F = F_n$ on $\nF =
2n+1$ vertices as follows: Let $F$ be obtained from the graph $H_n$ of even order $\nH = 2n$ defined in Claim I by adding a new vertex $x_{n+1}$ and joining it to every vertex in $X \setminus \{x_1\}$. Let $X_F = X \cup \{x_{n+1}\}$. For the proof, consider an arbitrary FD-set of $F$ and show that $|S| \ge \nF-2$. The proof to show that for an arbitrary FD-set $S$ of $F$ we have $|S| \ge \nF-2$ is similar to the proof presented in Claim I and is therefore omitted. [[($\Box$)]{}]{}

By Claim I and Claim II, there is an infinite family of graphs $G$ of order $n \ge 6$ with $\delta(G) \ge 1$ satisfying ${{\rm fd}}(G) = n - 2$, irrespective of whether $n$ is even or odd. [$\Box$]{}

Note that, by Claims I and II, for each integer $n \ge 6$, there is a connected graph $G$ on $n$ vertices satisfying ${{\rm fd}}(G) = n - 2$. If $n \in \{3,4,5\}$, we can simply take $G = C_n$. Hence for all $n \ge
3$, there exists a connected graph $G$ on $n$ vertices satisfying ${{\rm fd}}(G) = n - 2$.

Let $G$ be a graph of order $n$ with at least two edges. Let $G^*$ be the subgraph obtained from $G$ by deleting all isolated vertices in $G$, if any. Then, $\delta(G^*) \ge 1$ and $G^*$ has order $n^* \ge
3$. Applying Theorem \[thm\_n2\] to $G^*$, we have that ${{\rm fd}}(G^*)
\le n^*-2$. Since every ${{\rm fd}}(G^*)$-set can be extended to a FD-set in $G$ by adding to it the set of isolated vertices in $G$, we have that ${{\rm fd}}(G) \le n-2$. Hence as a consequence of Theorem \[thm\_n2\], we have the following result.

If $G$ is a graph of order $n$ and size at least $2$, then ${{\rm fd}}(G)
\le n-2$. \[c:bound\]

We next present some upper bounds on the fair domination number in terms of its order, chromatic number and average, maximum and minimum degrees. For this purpose, we first recall the Caro-Wei Theorem (see [@Ca79; @Wei81]).

[Caro-Wei Theorem.]{} For every graph $G$ of order $n$, $$\alpha(G) \ge \sum_{v \in V(G)} \frac{1}{1 + d_G(v)} \ge
\frac{n}{{{\overline{d}}}(G) + 1}.$$

For our purposes, we also need the following useful lower bound on the repetition number of a graph, established by Caro and West in [@CaWe09].

[Caro-West Lemma.]{} If $G$ is a graph of order $n$, then ${{\rm rep}}(G) \ge n/(2{{\overline{d}}}(G)
-2\delta(G) + 1)$.

Let $G$ be a graph of order $n$. Then the following holds.\
[(a)]{} If $n \ge 2$ and $\delta(G) \ge 1$, then ${{\rm fd}}(G) \le n - n/(({{\overline{d}}}(G) + 1) \Delta(G))$.\
[(b)]{} ${{\rm fd}}(G) \le n  - n/(2{{\overline{d}}}(G) - 2\delta(G) +1)\chi(G)$.\
[(c)]{} For $r \ge 2$, if $G$ is an $r$-regular graph, then ${{\rm fd}}(G)
\le rn/(r+1)$. \[prop2\]

**Proof.** (a) Let $B$ be a maximum independent set in $G$. Since $G$ has no isolated vertex, the set $V \setminus B$ is a dominating set in $G$. We now consider the degrees of the vertices of $B$. There are at most ${{\rm span}}(G)$ possible distinct values for these degrees, and so, by the Pigeonhole Principle, at least one value, say $q$, appears at least $\alpha(G)/{{\rm span}}(G)$ times. Let $Q$ be the set of all vertices in $B$ with degree $q$. Then, $Q \subseteq B$ and $|Q| = q$. Let $D = V \setminus Q$. Then, $D$ is a FD-set, and so ${{\rm fd}}(G) \le n
- |Q| \le n - \alpha(G)/{{\rm span}}(G)$. The desired result now follows from the observation that ${{\rm span}}(G) \le \Delta(G)$ and from the Caro-Wei Theorem.

\(b) Let ${{\rm rep}}(G) = m$ and suppose that $X =
\{v_1,\ldots,v_m\}$ is a set of vertices with the same degree in $G$. Let $H = G[X]$ be the subgraph induced by the set $X$. Clearly, $\chi(H) \le \chi(G)$, and so $\alpha(H) \ge m/\chi(H) \ge m/\chi(G)
\ge n/(2{{\overline{d}}}(G) -2\delta(G) +1)\chi(G)$ by the Caro-West Lemma. Let $Q$ be a maximum independent set in $H$, and so $|Q| = \alpha(H)$. Let $D = V(G) \setminus Q$. Then, $D$ is a FD-set in $G$, and so ${{\rm fd}}(G) \le n - |Q| \le n - \alpha(H)$, and the desired result follows.

\(c) Since $G$ is an $r$-regular graph, we note that ${{\overline{d}}}(G) =
\delta(G)$ and $\chi(G) \le r+1$ and the result follows from Part (b). [$\Box$]{}

Note that, in case that $G$ is a regular graph, the complement of a fair dominating set of $G$ is an induced regular subgraph of $G$. At this point, it is worth mentioning the famous Erdős-Fajtlowicz-Staton problem (see [@AlKrSu]) about the largest induced regular subgraph of a graph $G$. In the case when $G$ is regular, the complement of such a subgraph is a fair dominating set of $G$ .

For $r \ge 1$, if $G$ is an $r$-regular graph on $n$ vertices, then ${{\rm fd}}(G) \le n - c \log n$ for some $c > 0$. \[prop4\]

**Proof.** Let ${{\cal G}}_n$ denote the family of all graphs of order $n$. By Ramsey’s theory, for all graphs $G \in {{\cal G}}_n$ we have $\max \{ \alpha(G), \alpha({\overline{G}}) \} \ge c \log n$ for some constant $c$. For $r \ge 1$, let $G$ be an $r$-regular graph in ${{\cal G}}_n$. Then, $G$ contains either an independent set or a clique of order at least $c\log n$ for some constant $c$. Let $X$ be the vertex set of such an independent set or clique in $G$. Then, $|X| \ge c\log n$ and the subgraph $G[X]$ induced by $X$ is $s$-regular for some $s$. If $X$ is an independent set in $G$, then $s = 0$, while if $X$ is a clique, then $s = |X| - 1 \le r$. Further if $|X| - 1 = r$, then we note that $K_{r+1}$ is a component of $G$. On the one hand, if $s <
r$, then for every vertex $v \in X$, we have $|N(v) \cap (V
\setminus X)| = r-s > 0$ and hence $V \setminus X$ is a FD-set of $G$, and so ${{\rm fd}}(G) \le n - |X| \le n - c\log n$. On the other hand, if $s = r$, then we choose a vertex $v \in X$ and define $D = (V
\setminus X) \cup \{v\}$. Then the set $D$ is a FD-set of $G$, and so ${{\rm fd}}(G) \le n - |X| + 1 \le n - c\log n + 1 = n - c^*\log n$ for some constant $c^*$. [$\Box$]{}

If $G$ is a connected graph on $n \ge 6$ vertices satisfying ${{\rm fd}}(G)
= n - 2$, then $2 \le {{\rm rep}}(G) \le 4$. \[prop5\]

**Proof.** A well-known elementary exercise states that every graph of order at least two has two vertices with the same degree, and so ${{\rm rep}}(G) \ge 2$. Hence it suffices for us to prove that ${{\rm rep}}(G) \le 4$. Assume for the sake of contradiction, that ${{\rm rep}}(G)
\ge 5$. By Ramsey Theory, $r(K_3,K_3) = 6$. Further if $G$ is a graph on five vertices such that neither $G$ nor its complement ${\overline{G}}$ contains a copy of $K_3$, then $G = C_5$. Thus since ${{\rm rep}}(G) \ge 5$ there are either three vertices of the same degree in $G$ that induce an independent set or clique in $G$ or there are five vertices of the same degree in $G$ that induce a $C_5$. Let $X$ be the vertex set of such an independent set or clique in $G$ of cardinality $3$, if it exists; otherwise let $X$ be the vertex set of such an induced $5$-cycle in $G$. Then, $G[X]$ is $s$-regular with $s = 2$ or $s =
0$. Since $G$ is connected and the vertices in $X$ have all the same degree in $G$, they also must have the same number of neighbors in $V
\setminus X$ (which is non-empty since $n \ge 6$), implying that ${{\rm fd}}(G) \le n - 3$ or ${{\rm fd}}(G) \le n - 5$ in case case $G[X] =
C_5$. In all cases, we have ${{\rm fd}}(G) < n - 2$, a contradiction. Therefore, ${{\rm rep}}(G) \le 4$. [$\Box$]{}

We remark that the restriction on the order $n \ge 6$ in the statement of Proposition \[prop5\] is necessary since $G = C_5$ has order $n = 5$ and satisfies ${{\rm rep}}(G) = 5$ and ${{\rm fd}}(G) = 3 = n-2$. Both Proposition \[prop4\] and Proposition \[prop5\] give further evidence that a connected graph of large order achieving the upper bound in Theorem \[thm\_n2\] is highly non-regular. Further, Proposition \[prop4\] gives a better bound than Proposition \[prop2\](a) when $r \ge \sqrt{n/\log n}$ and a better bound than Proposition \[prop2\](b) when $\chi(G) \ge n/\log n$.

Trees
-----

In this section, we focus our attention on trees. We shall need the following notation. A vertex of degree one is called a *leaf* and its neighbor is called a *support vertex*. The set of support vertices of a tree $T$ is denoted by $S_T$, while the set of leaves by $L_T$. A neighbor of a vertex $v$ that is a leaf we call a *leaf-neighbor* of $v$. A *strong support vertex* is a vertex adjacent to at least two leaves. The *corona* of a graph $H$, denoted by ${{\rm cor}}(H)$, is the graph of order $2|V(H)|$ obtained from $H$ by attaching a leaf to each vertex of $H$. We note that every vertex of ${{\rm cor}}(H)$ is a leaf or is a support vertex with exactly one leaf-neighbor.

If we restrict our attention to trees, then the bound in Theorem \[thm\_n2\] can be improved significantly. For this purpose, we recall that a classical result of Ore [@o9] established that if $G$ is a graph of order $n$ with no isolated vertex, then $\gamma(G) \le n/2$. Further, Payan and Xuong [@px9] showed that the only connected graphs achieving equality in this bound are the $4$-cycle $C_4$ and the corona ${{\rm cor}}(H)$ for a connected graph $H$. We next establish an upper bound on the fair domination number of a tree and characterize the extremal trees. We begin with the following two observations.

Every 1FD-set in a graph contains all its strong support vertices. \[o:tree1\]

[**Proof.** ]{}Let $G$ be a graph and let $D$ be a 1FD-set in $G$. Let $v$ be an arbitrary strong support vertex in $G$. If $v \notin D$, then in order to dominate the leaf-neighbors of $v$, every leaf-neighbor of $v$ belongs to $D$. Since $v$ has at least two leaf-neighbors, this implies that $|N(v) \cap D| \ge 2$, a contradiction. Hence, $v \in
D$. [$\Box$]{}

If $T$ is the corona of a tree and $T$ has order $n$, then ${{\rm fd}}(T) =
n/2$. Further, $V(T)$ can be partitioned into two ${{\rm fd}}(T)$-sets. \[o:tree2\]

[**Proof.** ]{}The result is trivial for $n = 2$. Hence we may assume that $T$ is the corona of a tree and $n \ge 4$. Then, $\gamma(T) = n/2$ and we note that $|S_T| = |L_T| = n/2$. Further both sets $S_T$ and $L_T$ form a 1FD-set of $T$, and so ${{\rm fd}}(T) \le
{{\rm fd}_1}(T) \le n/2$. Since every FD-set of $T$ is a dominating set, we have that $n/2 = \gamma(T) \le {{\rm fd}}(T) \le n/2$. Consequently, we must have equality throughout this inequality chain. In particular, ${{\rm fd}}(T) = n/2$ and both $S_T$ and $L_T$ are ${{\rm fd}}(T)$-sets. [$\Box$]{}

We are now in a position to prove the following result. In the proof, we will deal with what we call *$3$-end-paths*, which are paths $xyz$ in a tree $T$ such that $x$ is a leaf, $N(y) = \{x,z\}$ and $d_T(z) \ge 2$. We will call $z$ the *base vertex* of the $3$-end-path. Note that, since every tree has at least two leaves, the corona of a tree on at least three vertices has at least two $3$-end-paths sharing at most their base vertices.

\[n/2\] If $T$ is a tree of order $n \ge 2$, then ${{\rm fd}_1}(T) \le n/2$ with equality if and only if $T$ is the corona of a tree. \[thm1\]

**Proof.** By Observation \[o:tree2\] if $T$ is the corona of a tree, then ${{\rm fd}}(T) = n/2$ and both $S_T$ and $L_T$ are 1FD-sets. We will prove the statement by induction on $n$. If $2 \le n \le 7$, this follows directly by checking all possible trees. This establishes the case cases. For the inductive hypothesis, let $n \ge
8$ and assume that every tree $T'$ of order $n'$, where $2 \le n' <
n$, satisfies ${{\rm fd}_1}(T) \le n'/2$, with equality only if $T'$ is the corona of a tree. Let $T$ be a tree of order $n$. If $T$ is a star $K_{1,n}$, then the central vertex of $T$ is a 1FD-set, implying that ${{\rm fd}}(T) = 1 < n/2$ and we are done. Hence we may assume that $T$ is not a star. Therefore, $T$ contains a vertex $w$ all of whose neighbors except for one, say $y$, are leaves. Let $t$ be the number of leaf-neighbors of $w$, and so $t = d(w) - 1$. We distinguish the following cases.

*Case 1. Suppose that $t = 1$*. Then, $d(w) = 2$. Let $z$ be the leaf-neighbor of $w$. Then, $ywz$ is a $3$-end-path in $T$ with $y$ as its base vertex. Let $T^* = T - \{w,z\}$ have order $n^*$, and so $n^* = n - 2$. Applying the inductive hypothesis to $T^*$, ${{\rm fd}_1}(T^*) \le n^*/2 = n/2 - 1$, with equality only if $T^*$ is the corona of a tree. Let $D^*$ be a ${{\rm fd}_1}(T^*)$-set. Suppose first that $T^*$ is not the corona of a tree. Then, $|D^*| <
n/2 - 1$. Moreover, $T$ is not the corona of a tree. If $y \in D^*$, then let $D = D^* \cup \{w\}$. If $y \notin D^*$, then let $D = D^*
\cup \{z\}$. In both cases $D$ is a 1FD-set of $T$, and so ${{\rm fd}_1}(T)
\le |D| < (n/2 -1) + 1 = n/2$, and we are done. Hence we may assume that $T^*$ is the corona of a tree. Then, $y$ is either a leaf or a support vertex of $T^*$.

Suppose that $y$ is a leaf of $T^*$. Since $T^*$ has at least five vertices, it contains at least two $3$-end-paths that are vertex disjoint or that have at most their base vertices in common. Therefore, $T^*$ contains a $3$-end-path, say $abc$ where $c$ is the base vertex of the path, that has no vertex from $N[y]$. We now consider the tree $T^{**} = T - \{a,b\}$. In $T^{**}$ we note that the vertex $y$ has degree $2$ and has no leaf neighbor. Hence, $T^{**}$ is not the corona of a tree. Applying the inductive hypothesis to $T^{**}$, ${{\rm fd}_1}(T^{**}) < n/2 - 1$. As above, every ${{\rm fd}_1}(T^{**})$ can be extended to a 1FD-set of $T$ by adding to it either $w$ or $z$, implying that ${{\rm fd}_1}(T) < n/2$ and we are done. Hence we may assume that $y$ is a support vertex of $T^*$. Then, $T$ is also a corona of a tree and hence, by Observation \[o:tree2\], ${{\rm fd}}(T) = n/2$ and we are done.

*Case 2. Suppose that $t \ge 2$*. Then evidently $T$ is not the corona of a tree. Let $x_1, x_2, \ldots x_t$ be the $t$ neighbor leaves of $w$ and let $T^* = T - \{x_1, x_2, \ldots, x_t\}$. Suppose first that $T^*$ is not the corona of a tree. Applying the induction hypothesis to $T^*$, we have that ${{\rm fd}}(T^*) < (n - t)/2$. Let $D^*$ be a ${{\rm fd}_1}(T^*)$-set. If $y \in D^*$, then let $D = D^*
\cup \{w\}$. If $y \notin D^*$, then $w \in D^*$ and let $D = D^*$. In both cases, $D$ is a 1FD-set of $T$, and so ${{\rm fd}}(T) \le |D| \le
|D^*| + 1 < (n - t)/2 + 1 \le n/2$, and we are done. Hence we may assume that $T^*$ is the corona of a tree. By Observation \[o:tree2\], ${{\rm fd}}(T^*) = (n - t)/2$ and $L_{T^*}$ is a ${{\rm fd}_1}(T^*)$-set. Since $w \in L_{T^*}$, it follows that $L_{T^*}$ is also a 1FD-set of $T$, implying that ${{\rm fd}}(T) \le (n-t)/2 < n/2$, and we are done. [$\Box$]{}

As an immediate consequence of Observation \[o:tree2\] and Theorem \[thm1\], we have the following result.

If $T$ is a tree of order $n \ge 2$, then ${{\rm fd}}(T) \le n/2$ with equality if and only if $T$ is the corona of a tree. \[c:thm1\]

Recall that the *$k$-domination number* $\gamma_k(G)$ of a graph $G$ is the cardinality of a minimum $k$-dominating set, i.e., a set $D$ of vertices such that every vertex outside $D$ has at least $k$ neighbors in $D$. In [@FiJa], Fink and Jacobson show that $\gamma_2(T) \ge \lceil (n+1)/2 \rceil$ holds for every tree $T$ on $n$ vertices. This fact and Theorem \[n/2\] allow us to prove that any minimum FD-set in a tree is a 1FD-set.

\[fd\_tree\] In a tree, every minimum FD-set is a 1FD-set.

**Proof.** Let $T$ be a tree and let $D$ be a ${{\rm fd}}(T)$-set. Then, $D$ is a kFD-set for some $k \ge 1$. Suppose that $k \ge 2$. Then, $|N(x) \cap D| = k \ge 2$ for all $x \in V \setminus D$, implying that $D$ is a $2$-dominating set of $T$ and thus $|D| \ge
\gamma_2(T)$. Hence by the result of Fink and Jacobson, we have that ${{\rm fd}}(T) = |D| \ge \gamma_2(T) \ge \lceil (n+1)/2 \rceil > n/2$, contradicting Theorem \[n/2\]. Hence, $k = 1$, and so $D$ is a 1FD-set. [$\Box$]{}

The set of non-leaves in a tree is a FD-set in the tree, implying the following observation.

If $T$ is a tree on $n \ge 3$ vertices with $\ell$ leaves, then ${{\rm fd}}(T) \le n - \ell$. \[o:tree\]

We remark that if a tree has more leaves than internal vertices, then the upper bound on the fair domination number of a tree given by Observation \[o:tree\] is better than the upper bound of Theorem \[n/2\]. The next theorem characterizes the trees where the set of non-leaves is not a minimum FD-set. If $H$ is a subtree of a tree $T$ such that $H$ is the corona of a tree, $H \ne T$ and $N(x)
\cap S_H = \emptyset$ for every vertex $x \in V \setminus V(H)$, then we call $H$ a *special corona-subtree* of $T$.

Let $T = (V,E)$ be a tree on $n \ge 3$ vertices with $\ell$ leaves. Then the following assertions are equivalent:\
${{\rm fd}}(T) < n - \ell$.\
For every ${{\rm fd}}(T)$-set $D$, there are two vertices in $V \setminus D$ that are adjacent.\
The tree $T$ contains a special corona-subtree. \[char:tree\]

[**Proof.** ]{}We show that $(i) \Rightarrow (ii) \Rightarrow (iii)
\Rightarrow (i)$. Let $D$ be an arbitrary ${{\rm fd}}(T)$-set. By Observation \[fd\_tree\], the set $D$ is a 1FD-set in $T$.

$(i) \Rightarrow (ii)$: Suppose that ${{\rm fd}}(T) < n - \ell$. Then, $D
\ne V \setminus L_T$ and thus either $D \subset V \setminus L_T$ (but $D \ne V \setminus L_T$) or $L_T \cap D \ne \emptyset$. Suppose $D
\subset V \setminus L_T$ and let $x \in V \setminus (D \cup L_T)$. Since $d_T(x) \ge 2$ and $|N(x) \cap D| = 1$, there is a vertex $y
\in N(x) \setminus D$ and (ii) holds. Hence we may assume that $L_T
\cap D \ne \emptyset$. Let $z \in L_T \cap D$ and let $N(z) = \{y\}$. If $y \in D$, then $D \setminus \{z\}$ is a 1FD-set in $T$, contradicting the minimality of $D$. Hence, $y \notin D$, implying that $N(y) \cap D = \{z\}$. Since $n \ge 3$, there is a vertex $x \in
N(y) \setminus D$ and, once again, (ii) holds.

$(ii) \Rightarrow (iii)$: Suppose that for every ${{\rm fd}}(T)$-set $S$ there are two vertices in $V \setminus S$ that are adjacent. Let $x$ and $y$ be two adjacent vertices in $V \setminus D$. We note that $x,
y \in V \setminus L_T$. Let $x' \in N(x) \cap D$ and $y' \in N(y)
\cap D$, and consider the subtree $T'= T[\{x,x',y,y'\}]$ of $T$. Then, $L_{T'} = V(T') \cap D = \{x,y\}$ and $S_{L'} = V(H) \setminus
L(T') = \{x,y\}$. Among all subtrees of $T$ containing $x$ and $y$ with the property that the leaves of the subtree are vertices of $D$, let $H$ be one of maximum order. Thus, $\{x,y\} \subset V(H)$, $L_H =
V(H) \cap D$ and $H$ is such a tree of maximum order. Let $S = V(H)
\setminus L_H$.

We show that $H$ is the corona of a tree. It suffices to show that $|N(u) \cap L_H| = 1$ for all $u \in S$. Let $u \in S$ and suppose first that $N(u) \cap L_H = \emptyset$. Since $L_H = V(H) \cap D$, there is a vertex $y \in V \setminus V(H)$ such that $y \in D$ and $y
\in N(u)$. But then adding the vertex $y$ and the edge $uy$ to the tree $H$ produces a tree $H'$ such that $\{x,y\} \subset V(H')$ and $L_{H'} = V(H') \cap D$, contradicting the maximality of $H$. Hence, $|N(u) \cap L_H| \ge 1$ for all $u \in S$. If $|N(u) \cap L_H| > 1$ for some $u \in S$, then $|N(u) \cap D| > 1$, contradicting the fact that $D$ is a 1FD-set. Hence, $|N(u) \cap L_H| = 1$ for all $u \in
S$, implying that $H$ is the corona of a tree and $S_H=S$. If $T$ is the corona of a tree, then by Observation \[o:tree2\], the set $S_T$ is a ${{\rm fd}}(T)$-set that does not satisfy (ii), a contradiction. Hence, $T$ is not the corona of a tree. Thus, $H \ne T$.

Let $z \in V \setminus V(H)$ and suppose that there is a vertex $v
\in N(z) \cap S$. Let $w$ be the vertex of $D$ that is adjacent to $z$ in $T$. Since $T$ is cycle-free, $w \in V \setminus V(H)$. But then adding the vertex $z$ and the edge $wz$ to the tree $H$ produces a tree $H'$ such that $\{x,y\} \subset V(H')$ and $L_{H'} = V(H')
\cap D$, contradicting the maximality of $H$. Hence, $N(z) \cap S =
\emptyset$. This is true for all vertices $z \in V \setminus V(H)$. Consequently, $H$ is a special corona-subtree of $T$, and so (iii) holds.

$(iii) \Rightarrow (i)$: Suppose that the tree $T$ contains a special corona-subtree $H$. Let $D = (V \setminus (L_T \cup S_H)) \cup (L_H
\cap L_T)$. Let $v \in V \setminus D = S_H \cup (L_T \setminus
V(H))$. If $v \in S_H$, then since $H$ is a special corona-subtree of $T$ and $L_H \subseteq D$, we have that $|N_T(v) \cap D| = |N_T(v)
\cap L_H| = 1$. If $v \in L_T \setminus V(H)$, then since the neighbor of $v$ in $T$ belongs to $D$, we once again have that $|N_T(v) \cap D| = 1$. Hence, $D$ is a 1FD-set of $T$, and so ${{\rm fd}}(T)
\le |D| = |V \setminus L_T| - |S_H| + |L_H \cap L_T|$. Since $H$ is a special corona-subtree of $T$, at least one leaf of $T$ is not a leaf of $H$. Therefore, $|L_H \cap L_T| < |L_H| = |S_H|$, implying that ${{\rm fd}}(T) < |V \setminus L_T| = n - \ell$, and so (i) holds. [$\Box$]{}

As an immediate consequence of Theorem\[char:tree\], we obtain the following characterization of the trees whose set of non-leaves is a minimum FD-set.

Let $T = (V,E)$ be a tree on $n \ge 3$ vertices with $\ell$ leaves. Then the following assertions are equivalent:\
${{\rm fd}}(T) = n - \ell$.\
There is a ${{\rm fd}}(T)$-set $D$ such that $V \setminus D$ is an independent set.\
The tree $T$ contains no special corona-subtree. \[char:treec\]

Maximal Outerplanar Graphs
--------------------------

A maximal outerplanar graph, abbreviated *MOP*, is a triangulation of the polygon. It is well-known that every bounded face of a MOP is a triangle. Further a MOP on $n$ vertices is $3$-colorable, $2$-degenerate (i.e., every subgraph contains a vertex with degree at most two), has exactly $2n-3$ edges and the neighborhood of every vertex of the graph induces a path (see [@HoSt; @KoWe]). In particular it follows that every MOP $G$ on $n$ vertices has $\delta(G) = 2$ and that the vertices of degree $2$ are independent when $n \ge 4$. Note also that ${{\overline{d}}}(G) = 4 - 6/n$ and hence from Proposition \[prop2\](b) it follows that ${{\rm fd}}(G) \le
14n/15$. With more effort, this bound can be improved to $17n/19$, as we will show in the next theorem. But first, we need to prove the following lemma.

\[bip\] If $G$ is a MOP on $n \ge 3$ vertices, then the vertices of degree $3$ induce a bipartite graph.

[**Proof.** ]{}We proceed by induction on $n$. If $n = 3$ or $n=4$, then the theorem holds trivially. This establishes the base cases. Let $n \ge
5$ and assume that in every MOP of order $n'$, where $3 \le n' < n$, the vertices of degree $3$ induce a bipartite graph. Let $G$ be a MOP on $n$ vertices. Since $G$ is maximal outerplanar, there is a vertex $x$ of degree $2$ whose deletion results in a graph $G^*$ on $n-1$ vertices which is again a MOP. Let $u$ and $v$ be the neighbors of $x$ in $G$. Then, $u$ and $v$ are adjacent. Further since the vertices of degree $2$ in $G$ are independent, we have that $d_G(u)
\ge 3$ and $d_G(v) \ge 3$. If $d_G(u) = 3$ and $d_G(v) = 3$, then $u$ and $v$ would be two adjacent vertices of degree $2$ in the MOP $G^*$ of order at least $4$, which is not allowed. Hence, renaming $u$ and $v$ if necessary, we may assume that $d_G(u) \ge 4$ and $d_G(v) \ge
3$. Let $B$ and $B^*$ be the sets of vertices of degree $3$ in $G$ and $G^*$, respectively. By the induction hypothesis, the set $B^*$ induces a bipartite graph. If $d_G(v) \ge 4$, then $B = B^* \setminus
\{u,v\}$ and $B$ induces also a bipartite graph in $G$, as desired. Hence we may assume that $d_G(v) = 3$. If $d_G(u) \ge 5$, then $u, v
\notin B^*$ and let $B = B^* \cup \{v\}$. If $d_G(u) = 4$, then let $B = (B^* \setminus \{u\}) \cup \{v\}$. In both cases, the vertex $v$ is adjacent to at most one vertex of degree $3$ in $G$, say $z$, and so $v$ can be added to a partite set of $G^*[B^*]$ that does not contain $z$, showing then that $G[B]$ is bipartite. [$\Box$]{}

We are now in a position to present the following upper bound on the fair domination number of a MOP.

If $G$ is a MOP on $n \ge 3$ vertices, then ${{\rm fd}}(G) < 17n/19$.

[**Proof.** ]{}For $n = 3$, then ${{\rm fd}}(G) = 1 < 17n/19$. Hence we may assume that $n \ge 4$. For $i = 2,3,4,5$, let $V_i$ denote the set of vertices of degree $i$ in $G$ and let $|V_i| = n_i$. Moreover let $t$ be the number of vertices of degree at least $6$ in $G$. Then, $n_2 +
n_3 + n_4 + n_5 + t = n$ and $2 n_2 + 3 n_3 + 4 n_4 + 5 n_5 + 6 t \le
2 m = 2 (2n - 3) = 4n - 6$, counting first vertices and then edges. If $n_2 \le 2n/19$, $n_3 \le 4n/19$, $n_4 \le 6n/19$ and $n_5 \le
6n/19$, then $$\begin{aligned}
4n-6 &\ge& 2 n_2 + 3 n_3 + 4 n_4 + 5 n_5 + 6 t \\
         &=& 2 n_2 + 3 n_3 + 4 n_4 + 5 n_5 + 6  (n - ( n_2 + n_3 + n_4 +  n_5 ))\\
         &=& 6n - 4 n_2 - 3 n_3 - 2 n_4 - n_5 \\
        &\ge& 6n - \frac{8}{19} n - \frac{12}{19} n - \frac{12}{19} n - \frac{6}{19} n \\
        & =&  4n,\end{aligned}$$ a contradiction. Hence, $n_2 > 2n/19$, $n_3 > 4n/19$, $n_4 > 6n/19$ or $n_5 > 6n/19$. Suppose first that $n_2 > 2n/19$. Then, as $n \ge
4$, the set $V_2$ is independent and is therefore an out-regular set, and so ${\xi_{\rm or}}(G) \ge n_2 > 2n/19$. Hence by Proposition \[prop1\], we have that ${{\rm fd}}(G) = n - {\xi_{\rm or}}(G) < 17n/19$. Suppose $n_3 > 4n/19$. Let $V_3'$ be a maximum independent subset of $V_3$. By Lemma \[bip\], the graph $G[V_3]$ is a bipartite graph, and so $|V_3'| \ge |V_3|/2 > 2n/19$. Since $V_3'$ is an out-regular set, we have that ${\xi_{\rm or}}(G) \ge |V_3'| > 2n/19$. Hence by Proposition \[prop1\], we have that ${{\rm fd}}(G) < 17n/19$. Suppose $n_4
> 6n/19$. Let $V_4'$ be a maximum independent subset of $V_4$. Since $G$ is $3$-colorable, we have that $|V_4'| \ge |V_4|/3 > 2n/19$. The set $V_4'$ is an out-regular set, and so ${\xi_{\rm or}}(G) \ge |V_4'| >
2n/19$, implying by Proposition \[prop1\] that ${{\rm fd}}(G) < 17n/19$. Analogously if $n_5 > 6n/19$, then ${{\rm fd}}(G) < 17n/19$. In all four cases, we have ${{\rm fd}}(G) < 17n/19$, as desired. [$\Box$]{}

Nordhaus-Gaddum-Type Bounds
---------------------------

In this section we consider Nordhaus-Gaddum-type bounds for the fair domination number of a graph.

\[t:NordG\] Let $G$ be a graph on $n$ vertices. Then the following holds.\
If $n \ge 5$, then $3 \le {{\rm fd}}(G) + {{\rm fd}}({\overline{G}}) \le
2n-4$ and both bounds are sharp.\
If $n \ge 4$, then $2 \le {{\rm fd}}(G) \cdot {{\rm fd}}({\overline{G}})
\le (n-2)^2$ and both bounds are sharp.

[**Proof.** ]{}We will first prove both upper bounds. Without loss of generality, we may assume that $G$ is connected, and so, by Theorem \[thm\_n2\], ${{\rm fd}}(G) \le n - 2$. If ${\overline{G}}$ has size $m({\overline{G}}) \ge 2$, then by Corollary \[c:bound\], ${{\rm fd}}({\overline{G}}) \le n
- 2$, and so ${{\rm fd}}(G) + {{\rm fd}}({\overline{G}}) \le 2n-4$ and ${{\rm fd}}(G) \cdot
{{\rm fd}}({\overline{G}}) \le (n-2)^2$, as desired. If $m({\overline{G}}) = 1$, then ${\overline{G}}= \overline{K}_{n-2} \cup K_2$ and $G = K_n - e$ for some edge $e$ of $K_n$. Hence, ${{\rm fd}}(G) = 1$ and ${{\rm fd}}({\overline{G}}) = n-1$, implying ${{\rm fd}}(G) + {{\rm fd}}({\overline{G}}) = n \le 2n -4$ and ${{\rm fd}}(G) \cdot {{\rm fd}}({\overline{G}}) = n
-1 \le (n-2)^2$ when $n \ge 4$. Finally, if $m({\overline{G}}) = 0$, then ${\overline{G}}= \overline{K_n}$ and $G = K_n$. In this case we have ${\rm fd}(G) + {{\rm fd}}({\overline{G}}) = 1 + n \le 2n-4$, for $n \ge 5$, and ${\rm
fd}(G) \cdot {{\rm fd}}({\overline{G}})  = n \le (n-2)^2$, for $n \ge 4$. In all cases, ${{\rm fd}}(G) + {{\rm fd}}({\overline{G}}) \le 2n-4$, for $n \ge 5$, and ${{\rm fd}}(G)\,
{{\rm fd}}({\overline{G}}) \le (n-2)^2$, for $n \ge 4$.

That the upper bounds are sharp may be seen as follows. For $n \ge 6$ even, let $G = H_{n/2}$, while for $n \ge 7$ odd, let $G =
F_{(n-1)/2}$ where the graphs $H_n$ and $F_n$ are defined as in the proof of Theorem \[thm\_n2\]. Then, $G$ has order $n$ and, as shown in the proof of Theorem \[thm\_n2\], ${{\rm fd}}(G) = n - 2$. Since the graph ${\overline{G}}$ is connected, by Theorem \[thm:Gbar\](a), we have that ${{\rm fd}}({\overline{G}}) = n - 2$, and so ${{\rm fd}}(G) + {{\rm fd}}({\overline{G}}) = 2n-4$ and ${{\rm fd}}(G)\, {{\rm fd}}({\overline{G}}) = (n-2)^2$. For $n = 4, 5$, we simply take $G =
C_n$, which satisfies ${{\rm fd}}(G) = {{\rm fd}}({\overline{G}}) = n - 2$.

For the lower bounds, we may assume, without loss of generality, that ${{\rm fd}}(G) \le {{\rm fd}}({\overline{G}})$. If ${{\rm fd}}(G) \ge 2$, then ${{\rm fd}}(G) + {{\rm fd}}({\overline{G}})
\ge 3$ and ${{\rm fd}}(G) \cdot {{\rm fd}}({\overline{G}}) \ge 2$. Hence we may assume that ${{\rm fd}}(G) = 1$. But then $G$ has a vertex of degree $n-1$, implying that ${\overline{G}}$ is not connected. Hence, ${{\rm fd}}({\overline{G}}) \ge 2$ and we obtain ${{\rm fd}}(G) + {{\rm fd}}({\overline{G}}) \ge 3$ and ${{\rm fd}}(G) \cdot {{\rm fd}}({\overline{G}}) \ge
2$. This establishes the desired lower bounds. That the lower bounds are sharp may be seen by taking $G = K_{1,n-1}$. [$\Box$]{}

We remark that if $G = K_4$, then $G$ has order $n = 4$ and ${{\rm fd}}(G) +
{{\rm fd}}({\overline{G}}) = 1 + 4 = 5 > 2n-4$. Hence the constraint on the order $n
\ge 5$ in the statement of Theorem \[t:NordG\](a) cannot be relaxed. Moreover neither can the condition $n \ge 4$ in Theorem \[t:NordG\](b) be relaxed since if $G = K_3$, then $G$ has order $n=3$ and we have ${{\rm fd}}(G) = 1$ and ${{\rm fd}}({\overline{G}}) = 3$, implying that ${{\rm fd}}(G)\, {{\rm fd}}({\overline{G}}) = 3 > (n-2)^2 = 1$.

Unions of Graphs
----------------

In this section we investigate the fair domination of disjoint unions of graphs. We shall prove.

Let $G_1,\ldots,G_k$ be $k \ge 1$ graphs. Let $H$ be the disjoint union $\bigcup_{i=1}^k G_i$ of $G_1,\ldots,G_k$ and let $H$ have order $n$. Then the following holds. Then, $${{\rm fd}}(H) - \sum_{i=1}^k {{\rm fd}}(G_i) \le \frac{1}{k} (k-1)(n-k),$$ and this bound is sharp for $k = 1,2$. \[union\]

**Proof.** For $k = 1$ the result is trivial since both sides of the inequality are zero. Hence we may assume that $k \ge 2$. Let $n_i = |V(G_i)|$ for $1 \le i \le k$. Renaming the graphs $G_1,\ldots,G_k$, if necessary, we may assume that $n_1 \le n_2 \le \cdots \le n_k$, and so $n_k \ge n/k$ and $n -
n_k \le (k-1)n/k$. Let $D_k$ be a ${{\rm fd}}(G_k)$-set. Then, $D_k \cup (V(H) \setminus V(G_k))$ is a FD-set of $H$ and thus $$\begin{array}{lcl}
{{\rm fd}}(H) - \sum_{i=1}^k {{\rm fd}}(G_i) & \le & \displaystyle{ |D_k| + n - n_k - \sum_{i=1}^k {{\rm fd}}(G_i)  } \\ { \vspace{0.2cm} }& = &  \displaystyle{ n - n_k - \sum_{i=1}^{k-1} {{\rm fd}}(G_i)    }  \\   { \vspace{0.2cm} }& \le &  \displaystyle{ n - n_k - (k-1)}\\ { \vspace{0.2cm} }& \le & \displaystyle{ \frac{1}{k} (k-1)(n-k).}
\end{array}$$

This establishes the desired upper bound.

We show next that the bound is sharp for $k = 2$. For $n \ge 3$, let $G_1 = K_{1,2n-1}$ and let $G_2 = K_{2,n-1,n-1}$. Let $H = G_1 \cup
G_2$, and so $H$ has order $4n$. We note that there are only two values of $\ell$ for which $G_1$ has an $\ell$FD set $D$ different from $V(G_1)$. The first value of $\ell$ is $\ell =
1$ when $D$ consists of the central vertex of $G_1$ and any set of $t$ leaves, where $0 \le t \le 2(n-1)$. The second value of $\ell$ is $\ell = 2n-1$ when $D$ consists of all leaves in $G_1$. Hence, $\ell \in \{1,2n-1\}$. In particular, we note that ${{\rm fd}}(G_1) = 1$. Next we consider the graph $G_2$. Since $G_2$ has no dominating vertex adjacent to every other vertex, we note that $G_2$ has no $\ell$FD-set for $\ell \in \{1,2n-1\}$. In particular, ${{\rm fd}}(G_2) \ge
2$. However the partite set of cardinality $2$ is a FD-set in $G_2$, and so ${{\rm fd}}(G_2) \le 2$. Consequently, ${{\rm fd}}(G_2) = 2$. From our earlier observations, a FD-set of $H$ is formed by either taking a FD-set in $G_1$ and all vertices in $G_2$ or by taking a FD-set in $G_2$ and all vertices in $G_1$. Therefore, ${{\rm fd}}(H) \le
\min \{{{\rm fd}}(G_1) + |V(G_2)|, {{\rm fd}}(G_2) + |V(G_1)|\} = 2n+1$. Thus, $${{\rm fd}}(H) - \sum_{i=1}^k {{\rm fd}}(G_i) = 2(n-1) = \frac{1}{2} (4n-2) = \frac{1}{k} (k-1)(|V(H)|-k),$$ realizing the upper bound for $k = 2$. [$\Box$]{}

We remark that the fair domination number is highly sensitive with respect to edge deletion or edge addition. For $n \ge 3$, let $G_1 =
K_{1,2n-1}$ and let $G_2 = K_{2,n-1,n-1}$. Let $v_1$ denote the central vertex of $G_1$ and let $\{u_2,v_2\}$ be the partite set of $G_2$ of cardinality $2$. Let $H = G_1 \cup G_2$, and so $H$ has order $4n$, and let $G = H + u_2v_2$. As shown in the proof of Theorem \[union\], we have that ${{\rm fd}}(H) = 2n+1$. However the set $\{v_1,v_2\}$ is a FD-set of $G$ since every vertex in $V(G)
\setminus \{v_1,v_2\}$ is adjacent to exactly one of $v_1$ and $v_2$. Hence, ${{\rm fd}}(G) = 2$. Therefore we have the following observation.

There exists infinitely many graph $G$ such that ${{\rm fd}}(G + e) - {{\rm fd}}(G)
\ge |V(G)|/2 - 1$ for some edge $e \in E({\overline{G}})$. \[sensitive\]

Closing Remarks and Open Questions
==================================

This paper, in which we introduce the notion of fair domination, suggests many possible direction of further research. We close with the following list of open problems that we have yet to settle.

Find a polynomial time algorithm to compute ${{\rm fd}}(T)$ for trees $T$.

Improve upon the bounds of Proposition \[prop2\]. In particular, find best possible upper bounds for MOP’s, maximum planar graphs and regular graphs.

Find ${{\rm fd}}(G)$ for other families of graphs $G$, in particular the grid $P_n \times P_m$ and the torus $C_n \times C_m$.

Is it true that Theorem \[union\] is sharp also for $k \ge 3$?

In view of Proposition \[sensitive\], find the exact value of $\max |{{\rm fd}}(G+ e) - {{\rm fd}}(G)|$ over all graphs $G$ on $n$ vertices.

Characterize the graphs $G$ on $n$ vertices for which ${{\rm fd}}(G) = n-2$.

What can be said about the fair domination number ${{\rm fd}}(G)$ of the random graph $G(n,p)$?

[99]{}

N. Alon, M. Krivelevich, and B. Sudakov, Large nearly regular induced subgraphs. *SIAM J. Discrete Math.* **22** (2008), no. 4, 1325–1337.

D. M. Cardoso and M. Kaminski, V. Lozin, Maximum $k$-regular induced subgraphs. *J. Comb. Optim.* **14** (2007), no. 4, 455–463.

Y. Caro, New results on the independence number. *Tech. Report*, *Tel-Aviv University* (1979).

Y. Caro and D. B. West, Repetition number of graphs. *Electronic J. Combin.* **16** (2009) \#R7.

B. Csaba, Regular spanning subgraphs of bipartite graphs of high minimum degree. *Electron. J. Combin.* [ **14**]{} (2007), no. 1, Note 21, 7 pp. (electronic).

A. Hoffmann and L. Volkmann, On regular factors in regular graphs with small radius. *Electron. J. Combin.* **11** (2004), no. 1, Research Paper 7, 7 pp. (electronic).

J. F. Fink and M. S. Jacobson, $n$-Domination in graphs. *Graph Theory with Applications to Algorithms and Computer Science.* John Wiley and Sons. New York (1985), 282-300.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (eds), *Fundamentals of Domination in Graphs*, Marcel Dekker, Inc. New York, 1998.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (eds), *Domination in Graphs: Advanced Topics*, Marcel Dekker, Inc. New York, 1998.

G. Hopkins and W. Staton, Outerplanarity without topology, Bull. Inst. Combin. Appl. **21** (1997), 112–116.

A. Kostochka and D. B. West, Every outerplanar graph is the union of two interval graphs. *Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing* (Boca Raton, FL, 1999). Congr. Numer. **139** (1999), 5–8.

O. Ore, *Theory of graphs*. *Amer. Math. Soc. Transl.* **38** (Amer. Math. Soc., Providence, RI, 1962), 206–212.

C. Payan and N. H. Xuong, Domination-balanced graphs. *J. Graph Theory* **6** (1982), 23–32.

V. K. Wei, A lower bound on the stability number of a simple graph. *Bell Lab. Tech. Memo.* No. 81-11217-9 (1981).
