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 $v\in V(G)$, either $v\in D$ or $(v,d)\in E(G)$ for some $d\in D$. The cardinality redundance of a vertex set $S$, $CR(S)$, is the number of vertices 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 that achieves $CR(G)$ is a ${\gamma }_{cr}$-set, and the size of the minimum ${\gamma }_{cr}$-set is ${\gamma }_{cr}(G)$. 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$, $1$, or $2$, we give the minimum and 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$.

Supported by DMS-1560019