All Title Author
Keywords Abstract


Connected domination dot-critical graphs

Full-Text   Cite this paper   Add to My Lib

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.

Full-Text

comments powered by Disqus