Abstract

A signed graph (or sigraph in short) S is a graph G in which each edge x carries a value s(x) ? {+1, ?1} called its sign denoted specially as S = (G, s). Given a sigraph S, a new sigraph CE(S), called the common-edge sigraph of S is that sigraph whose vertex-set is the set of pairs of adjacent edges in S and two vertices of CE(S) are adjacent if the corresponding pairs of adjacent edges of S have exactly one edge in common, and the sign of the edge is the sign of the common edge. If all the edges of the sigraph S carry + sign then S is actually a graph and the corresponding common-edge sigraph is termed as the common-edge graph. In this paper, algorithms are defined to obtain a common-edge sigraph and detect whether it is balanced or not in O(n3) steps which will be optimal in nature.

References

• Acharya B . D, 1980, (1980b) Applications of sigraphs in behavioral sciences, MRI Technical Report DST/HCS. .
• Acharya B. D, 1983, A characterization of consistent marked graphs, Nat. Acad. Sci. -Letters, India.
• Acharya, B. D and Acharya, M, 1983, A graph-theoretical model for the analysis of intergroup stability in a social system, Manuscript. In: A mathematical bibliography of signed and gain graphs and allied areas, VII Edition.
• Acharya, B. D and Acharya, M, 1986, New algebraic models of a social system, Indian Journal of Pure and Applied Mathematics.
• Acharya, M and Sinha, D, 2005, Characterizations of line sigraphs, Nat. Acad. Sci. –Letters.
• Acharya, M and Sinha, D, 2006, Common-edge sigraphs, AKCE Int. J. Graphs Comb.
• Balbuena, C, Garcia-Vazquez, P. 2004, Edge-connectivity in Pk - path graphs, Discrete Mathematics.
• Behzad, M. and Chartrand, G. T , 1969, Line coloring of signed graphs, Elem. Math.
• Broersma, H. J. , HOEDE, C. , 1989, Path graphs, Journal of Graph Theory.
• Cartwright, D. and Harary, F. , 1956, Structural Balance: A generalization of Heider's Theory, Psych. Rev.
• Chartrand, G. T. , 1977, Graphs as Mathematical Models, Prindle, Weber and Schmidt, Inc. , Boston, Massachusetts.
• Cormen, Thomas, Leiserson, Charles. , Rivest, Ronald. , Stein, Clifford. , 2011, Introduction to algorithm, Third Edition, PHI Learning Private Limited.
• Deo, Narasing. , 1995, Graph theory with application to Engineering and Computer Science, Prentice Hall India.
• Doreian, P. , (1979/80), On the evolution of group and network structure, Social Networks.
• Doreian, P. , and Mrvar, A. , 1996, A partitioning approach in structural balance, Social Networks.
• Doreian, P. , 2002, Event sequences as generators of social network evolution, Social Networks.
• Harary, F. , Norman, R. Z. , Cartwright, R. W. , 1965, Structural Models: An Introduction to the Theory of Directed Graphs, Wiley Inter Science, Inc. , New York.
• Harary, F. , 1969, Graph Theory, Addison-Wesley Publ. Comp. , Reading, Massachusetts.
• Harary, F. , and Kabell, J. A. , 1980/81, A simple algorithm to detect balance in signed graphs, Math. Soc. Sci.
• Holland, L. W. , and Leinhardt, S. , 1977, Social structure as a network process, Zeitschrift f¨ur Soziologi´e.
• Horowitz, Ellis. , Sahni, Sartaj. , 2004, Computer Algorithm, Galgotia Publications, 2004 Edition.
• Kanetkar, Yashavant. , 2004, "Let Us C", Fifth Edition, BPB Publications.
• Kanetkar, Yashavant. , 2008, "Graphics under C", Fifth Edition, BPB publications.
• Kovchegov, V. B. , 1993, A model of dynamics of group structure of human institutions, Journal of Mathematical Sociology.
• Kovchegov, V. B. , 1994, A principle of nonergodicity for modeling of the human groups by nets of probability automata, Proceeding of the 14th IMACS World Conference on Computational and Applied Mathematics.
• Kovchegov, V. B. , 2004, Application of the theory of locally interacting and product potential networks of automata to modelling balance in social groups, Preprint.
• Li, H. , Lin, Y. , 1993, On the characterization of path graphs, Journal of Graph Theory.
• Li, X. , Zhao, B. , 2004, Isomorphisms of Pk – graphs for k ? 4, Discrete Mathematics.
• Lehot, P. G. H. , 1974, An optimal algorithm to detect a line graph and output its root graph, Journal of the Association for Computing Machinery.
• Sinha, D. , 2005, New frontiers in the theory of signed graph, Ph. D. Thesis, University of Delhi (Faculty of Technology).
• Sinha, D. , Upadhayaya, S. , Kataria, P. , 2013, Characterization of Common edge signed graphs, Applied Discrete Mathematics.
• Kulli, V. R. , 1973, On common-edge graphs, The Karnatak University Journal: Science XVIII.
• West, D. B. , 1996, Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd.
• Zasalavsky, T. , 1981, Characterizations of signed graphs, J. Graph Theory.
• Zasalavsky, T. , 1982, Signed graphs, Discrete Appl. Math