Matching properties in connected domination critical graphs

详细信息    查看全文

• 作者：Nawarat Ananchuen ; Watcharaphong Ananchuen ; Michael D. Plummer
• 关键词：Connected domination ; Critical edge ; Matching ; Factor-critical ; Bicritical ; 3-factor-critical ; Claw-free
• 刊名：Discrete Mathematics
• 出版年：2008
• 出版时间：6 April 2008
• 年：2008
• 卷：308
• 期：7
• 页码：1260-1267
• 全文大小：184 K

文摘

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph facee10a4"" title=""Click to view the MathML source"">G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.

A graph G is factor-critical if G-v has a perfect matching for every vertex vV(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,vV(G) or, more generally, k-factor-critical if, for every set SV(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1–13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1–13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].