## 1月27日　吕长虹教授学术报告（数统学院）

 报 告 人：吕长虹 教授报告题目：Algorithmic aspects ofpaired-domination problem of graphs报告时间：2018年1月27日（周六）15：30报告地点：静远楼1506报告厅主办单位：数学与统计学院、科技处报告摘要：        Let $G=(V, E)$ be a simple connectedgraph. A set $S\subseteq V(G)$ is called a paired-dominating set if everyvertex in $V(G)\setminus S$ has at least one neighbor in $S$ and the subgraphinduced by $S$ contains a perfect matching.        The paired-domination number of $G$,denoted by $\gamma_{pr}(G)$, is the minimum cardinality of a paired-dominatingset of $G$.        In this talk, we will survey thealgorithmic results of paired-domination problem on subclasses of chordalgraphs,  NP-completeness and APX-completenessresults.