solidot新版网站常见问题,请点击这里查看。

Independent transversal domination number of a graph. (arXiv:1704.06093v1 [math.CO])

来源于:arXiv
Let $G=(V, E)$ be a graph. A set $S\subseteq V(G)$ is a {\it dominating set} of $G$ if every vertex in $V\setminus S$ is adjacent to a vertex of $S$. The {\it domination number} of $G$, denoted by $\gamma(G)$, is the cardinality of a minimum dominating set of $G$. Furthermore, a dominating set $S$ is an {\it independent transversal dominating set} of $G$ if it intersects every maximum independent set of $G$. The {\it independent transversal domination number} of $G$, denoted by $\gamma_{it}(G)$, is the cardinality of a minimum independent transversal dominating set of $G$. In 2012, Hamid initiated the study of the independent transversal domination of graphs, and posed the following two conjectures: Conjecture 1. If $G$ is a non-complete connected graph on $n$ vertices, then $\gamma_{it}(G)\leq\lceil\frac{n}{2}\rceil$. Conjecture 2. If G is a connected bipartite graph, then $\gamma_{it}(G)$ is either $\gamma(G)$ or $\gamma(G)+1$. We show that Conjecture 1 is not true in general. Very r 查看全文>>