Extremal Problems Related to the Cardinality-Redundance of Graphs

Abstract

A dominating set of a graph $G$ is a set of vertices $D$ such that for all $\nu \in V(G)$, either $\nu \in D$ or $[\nu ,d]\in E(G)$ for some $d\in D$. The cardinality-redundance of a vertex set $S$, $CR(S)$, is the number of vertices $x\in V(G)$ such that $|N[x]\cap S|\ge 2$. The cardinality-redundance of $G$ is the minimum of $CR(S)$ taken over all dominating sets $S$. A set of vertices $S$ such that $CR(S)=CR(G)$ is a ${\gamma }_{CR}$-set, and the size of a minimum ${\gamma }_{CR}$-set is denoted ${\gamma }_{CR}(G)$.

Here, we are concerned with extremal problems concerning cardinality-redundance. We give the maximum number of edges in a graph with a given number of vertices and given cardinality-redundance. In the cases that $CR(G)=0$ or $1$, we give the minimum and maximum number of edges of graphs when ${\gamma }_{CR}(G)$ is fixed, and when $CR(G)=2$, we give the maximum number of edges of graphs where ${\gamma }_{CR}(G)$ is fixed. We give the minimum and maximum values of ${\gamma }_{CR}(G)$ when the number of edges are fixed and $CR(G)=0,1$, and we give the maximum values of ${\gamma }_{CR}(G)$ when the number of edges are fixed and $CR(G)=2$.