CN EN

理学院2018-2019学年夏季第二周学术报告(14)


学 术 报 告


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


报告学者:徐守军教授


报告者单位兰州大学


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


报告地点学生活动中心十层1005-3


摘要: 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联系邮箱:jjhu@bjtu.edu.cn