Connected domination dot-critical graphs
Abstract
A dominating set in a graph G=(V(G),E(G)) is a set D of vertices
such that every vertex in V(G)\ D has a neighbor in D. A
connected dominating set of a graph G is a dominating set whose
induce subgraph is connected. The connected domination number
gamma_c(G) is the minimum number of vertices of a connected
dominating set of G. A graph G is connected domination
dot-critical (cdd-critical) if contracting any two adjacent vertices
decreases gamma_c(G); and G is totally connected domination
dot-critical (tcdd-critical) if contracting any two vertices decreases
gamma_c(G). We provide characterizations of tcdd-critical graphs
for the classes of block graphs, split graphs and unicyclic graphs and
a characterization of cdd-critical cacti.
such that every vertex in V(G)\ D has a neighbor in D. A
connected dominating set of a graph G is a dominating set whose
induce subgraph is connected. The connected domination number
gamma_c(G) is the minimum number of vertices of a connected
dominating set of G. A graph G is connected domination
dot-critical (cdd-critical) if contracting any two adjacent vertices
decreases gamma_c(G); and G is totally connected domination
dot-critical (tcdd-critical) if contracting any two vertices decreases
gamma_c(G). We provide characterizations of tcdd-critical graphs
for the classes of block graphs, split graphs and unicyclic graphs and
a characterization of cdd-critical cacti.
PID: http://hdl.handle.net/10515/sy54j0bc0
Contributions to Discrete Mathematics. ISSN: 1715-0868