Connected domination in a signed graph and its complement

Article type: Research Article

Authors: Jeyalakshmi, P.^{; *} | Karuppasamy, K.

Affiliations: Department of Mathematics, Kalasalingam Academy of Research and Education, Anand Nagar, Krishnankoil, India

Correspondence: [*] Corresponding author. P. Jeyalakshmi, Department of Mathematics, Kalasalingam Academy of Research and Education, Anand Nagar, Krishnankoil - 626126, India. E-mail: jeyalakshmi.p@klu.ac.in.

Abstract: A signed graph Σ = (G, σ) is a graph with a sign attached to each arc. A subset S of V (Σ) is called a dominating set of Σ if |N+ (v)  ∩ S| > |N- (v)  ∩ S| for all v ∈ V - S . A dominating set S ⊆ V is a connected dominating set of Σ if <S> is connected. The minimum cardinality of a connected dominating set of Σ denoted by γsc, is called the connected domination number of Σ . In this paper, we introduce the connected domination number in a signed graph Σ and study different bounds and characterization of the connected domination number in a signed graph Σ . Furthermore, we find the best possible upper and lower bounds for γsc(Σ)+γsc(Σαc) where Σ is connected.

Keywords: Signed graph, dominating set, connected dominating set, connected domination number

DOI: 10.3233/JIFS-223857

Journal: Journal of Intelligent & Fuzzy Systems, vol. 45, no. 1, pp. 345-356, 2023