Extremal perfect graphs for a bound on the domination number

详细信息    查看全文

• 作者：Mostafa Blidia ; Mustapha Chellali ; Fré ; dé ; ric Maffray
• 关键词：Domination ; Bipartite ; Chordal ; Extremal graph
• 刊名：Discrete Mathematics
• 出版年：2008
• 出版时间：28 May 2008
• 年：2008
• 卷：308
• 期：10
• 页码：1785-1791
• 全文大小：162 K

文摘

We examine classes of extremal graphs for the inequality γ(G)|V|-max{d(v)+β_v(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and β_v(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs.