学 术 报 告

报告题目:The complexity of total edge domination and some related results on trees



报告时间2019年7月11日 下午6:30---7:10


摘要: Let $G$ be a connected graph with vertex set $V$ and edge set $E$. An edge subset $F\subseteq E$ is a {\em total edge dominating set} (resp. {\em edge dominating set}) if every edge $e\in E$ (resp. $e\in E\setminus F$) is adjacent to at least one edge in $F$. The minimum cardinality of a total edge dominating set (resp. edge dominating set) of $G$ is called the {\em total edge domination number} (resp. {\em edge domination number}) of $G$.  The {\em total edge dominating problem} is to find a minimum total edge dominating set of $G$. We prove that the total edge dominating problem is NP-complete for bipartite graph with maximum degree 3, and design a linear-time algorithm for solving this problem in a tree. We also present sharp upper and lower bounds on the total edge domination number in trees in terms of edge domination number and then characterize the extremal trees.



胡佳骥  理学院科研秘书联系电话:51688469联系邮箱