Connected domination: vertex criticality and matchings (Q2839672)

All over this paper the graphs are finite, simple, undirected and connected. Let \(G=(V(G), A(G))\) be a graph, a set \(S\subseteq V(G)\) is a dominating set for \(G\) if every vertex of \(G\) either belongs to \(S\) or is adjacent to a vertex of \(S\); if the subgraph of \(G\) induced by the dominating set \(S\) is connected, \(S\) is a connected dominating set for \(G\). \(\gamma_c(G)\) denotes the connected domination number of \(G\), that is: the minimum cardinality of a connected domination set for \(G\). \(G\) is said to be \(k\)-\(\gamma\)-connected-vertex-critical (abbreviated ``kcvc'') if \(\gamma_c(G)=k\), but \(\gamma_c(G-v)\leq k-1,\) for every vertex \(v\in V(G)\). A perfect (respectively near-perfect) matching in \(G\) is a matching which covers all (respectively, all but one) of the vertices of \(G\). \(G\) is factor-critical if \(G-v\) contains a perfect matching for every vertex \(v\in V(G)\). \(G\) is bicritical if \(G-u-v\) contains a perfect matching for every choice of two distinct vertices \(u, v\in V(G)\). \(G\) is \(k\)-factor-critical if \(G-S\) contains a perfect matching for every set \(S\subseteq V(G)\) with \(|S|=k\). If \(G\) contains no \(K_{1, t}\) as an induced subgraph, \(G\) is called \(K_{1, t}\)-free.NEWLINENEWLINENEWLINE The main results of this paper establish the following assertions:NEWLINENEWLINENEWLINE 1) Any \(K_{1,7}\)-free 3cvc graph \(G\) contains a perfect matching, whenever \(G\) is of even order and contains a near-perfect matching otherwise.NEWLINENEWLINENEWLINE 2) Any \(K_{1,4}\)-free 3cvc graph of even order is bicritical.NEWLINENEWLINENEWLINE 3) Any \(K_{1,5}\)-free 5-connected 3cvc graph of even order is bicritical.NEWLINENEWLINENEWLINE 4) Any \(K_{1,6}\)-free 3cvc graph of odd order is factor-critical.NEWLINENEWLINENEWLINE 5) Any \(K_{1,3}\)-free 3cvc graph of odd order and minimum degree at least 4 is 3-factor-critical.NEWLINENEWLINEThe authors show that the hypotheses of these theorems are best possible by illustrating them with several examples.NEWLINENEWLINENEWLINE This work expands (in some way) the results collected in previous papers by the same authors. The proof techniques presented here are also new with respect to the ordinary domination case.