The common minimal dominating signed graph

Document Type : Research Paper


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


‎‎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‎.


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)