Document Type : Research Paper

**Authors**

Dept. of Mathematics, Acharya Institute of Technology, Bangalore-560 090, India

**Abstract**

In this paper, we define the common minimal dominating signed graph of a given signed graph and offer a structural characterization of common minimal dominating signed graphs. In the sequel, we also obtained switching equivalence characterizations: $\overline{S} \sim CMD(S)$ and $CMD(S) \sim N(S)$, where $\overline{S}$, $CMD(S)$ and $N(S)$ are complementary signed graph, common minimal signed graph and neighborhood signed graph of $S$ respectively.

**Keywords**

**Main Subjects**

R. P. Abelson and M. J. Rosenberg (1958). Symoblic psychologic: A model of
attitudinal cognition. *Behav. Sci.*. 3, 1-13 F. Barahona, M. Grotschel, M. Junger, and G. Reinelt (1988). An application of combinatorial
optimization to statistical physics and circuit layout
design. *Operations Research*. 36 (3), 493-513 C. Berge (1962). Theory of Graphs and its Applications. *Methuen, London*. D. Cartwright and F. Harary (1956). Structural Balance: A Generalization of Heider’s
Theory. *Psychological Review*. 63, 277-293 E. J. Cockayne and S. T. Hedetniemi (1977). Towards a theory of domination in graphs. *Networks*. 7, 247-261 C. F. De Jaenisch (1862). Applications de l’Analyse mathematique an Jen des Echecs. D. Easley and J. Kleinberg (2010). Networks, Crowds, and Markets: Reasoning About
a Highly Connected World. *Cambridge University Press*. F. Harary (1969). Graph Theory. *Addison-Wesley Publishing Co.*. F. Harary (1953). On the notion of balance of a signed graph. *Michigan Math. J.*. 2, 143-146 F. Harary (1957). Structural duality. *Behav. Sci.*. 2 (4), 255-265 F. Heider (1946). Attitudes and Cognitive Organisation. *Journal of Psychology*. 21, 107-112 V. R. Kulli and B. Janakiram (1996). The common minimal
dominating graph. *Indian J. Pure Appl. Math.*. 27 (2), 193-196 V. R. Kulli and B. Janakiram (1998). On common minimal
dominating graphs. *Graph Theory Notes of New York*. XXXIV, 9-10 O. Ore (1962). Theory of Graphs. *Amer. Math. Soc. Colloq. Publ.*. 38 R. Rangarajan and P. Siva Kota Reddy (2010). The edge
$C_4$ signed graph of a signed graph. *Southeast Asian
Bulletin of Mathematics*. 34 (6), 1077-1082 R. Rangarajan, M. S. Subramanya and P. Siva Kota
Reddy (2012). Neighborhood signed graphs. *Southeast Asian Bulletin
of Mathematics*. 36 (3), 389-397 W. W. Rouse Ball (1982). Mathematical Recreation and Problems of Past and Present Times. E. Sampathkumar (1984). Point signed and line signed graphs. *Nat.
Acad. Sci. Letters*. 7 (3), 91-93 E. Sampathkumar, P. Siva Kota Reddy and M. S.
Subramanya (2010). Directionally $n$-signed graphs. *Ramanujan Math. Soc., Lecture Notes
Series (Proc. Int. Conf. ICDM 2008)*. 13, 155-162 E. Sampathkumar, P. Siva Kota Reddy and M. S. Subramanya (2009). Directionally $n$-signed graphs-II. *International J. Math. Combin.*. 4, 89-98 E. Sampathkumar, M. S. Subramanya and P. Siva Kota Reddy (2011). Characterization of line sidigraphs. *Southeast Asian Bulletin of Mathematics*. 35 (2), 297-304 P. Siva Kota Reddy and M. S. Subramanya (2009). Note on path signed graphs. *Notes on Number Theory and Discrete Mathematics*. 15 (4), 1-6 P. Siva Kota Reddy, S. Vijay and V. Lokesha (2009). $n^{th}$ Power signed graphs. *Proceedings of the Jangjeon
Math. Soc.*. 12 (3), 307-313 P. Siva Kota Reddy (2010). $t$-Path Sigraphs. *Tamsui Oxford
J. of Math. Sciences*. 26 (4), 433-441 P. Siva Kota Reddy, E. Sampathkumar and M. S. Subramanya (2010). Common-edge signed graph of a
signed graph. *J. Indones. Math. Soc.*. 16 (2), 105-112 P. Siva Kota Reddy, B.
Prashanth, and T. R. Vasanth Kumar (2011). Antipodal signed directed
Graphs. *Advn. Stud. Contemp. Math.*. 21 (4), 355-360 P. Siva Kota Reddy and B. Prashanth (2012). $\mathcal{S}$-Antipodal signed graphs. *Tamsui Oxford J. of Inf. Math. Sciences, to appear.*. 28 (2) P. Siva Kota Reddy and S. Vijay (2012). The super line signed graph $\mathcal{L}_r(S)$ of a signed Graph. *Southeast Asian Bulletin of Mathematics, to appear.*. 36 (5) P. Sol$\acute{e}$ and T. Zaslavsky (1994). A coding approach to signed graphs. *SIAM J. Discrete
Math.*. 4, 544-553 T. Soz$\acute{a}$nsky (1980). Enueration of weak isomorphism
classes of signed graphs. *J. Graph Theory*. 4 (2), 127-144 G. Toulouse (1977). Theory of the frustration effect in spin
glasses: I. *Commun. on Phys.*. 2, 115-119 A. M. Yaglom and I. M. Yaglom (1964). Challenging mathematical problems with elementary solutions. *Combinatorial Analysis and Probability Theory*. 1 T. Zaslavsky (1982). Signed graphs. *Discrete Appl. Math.*. 4 (1), 47-74 T. Zaslavsky (1998). A mathematical bibliography of signed and gain graphs and its allied areas. *Electronic
J. Combin., Dynamic Surveys, No. DS8.*. 8 (1)

September 2012

Pages 39-46

**Receive Date:**06 September 2012**Revise Date:**12 October 2012**Accept Date:**12 October 2012**Published Online:**01 September 2012