solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看214次
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 查看全文>>