A Note on Connected Domination Critical Graphs

J. David Taylor1, Lucas C. van der Merwe1
1Department of Mathematics, University of Tennessee at Chattanooga Chattanooga, TN 37403 USA

Abstract

Let \( \gamma_c(G) \) denote the connected domination number of the graph \( G \). A graph \( G \) is said to be connected domination edge critical, or simply \( \gamma_c \)-critical, if \( \gamma_c(G + e) < \gamma_c(G) \) for each edge \( e \in E(\overline{G}) \). We answer a question posed by Zhao and Cao concerning \( \gamma_c \)-critical graphs with maximum diameter.

Keywords: Diameter, connected domination, edge addition, edge critical AMS subject classification: 05C35, 05C69, 05C75