Authors and affiliations
Data in the social sciences can often modeled using signed graphs, graphs where every edge has a sign + or −, or marked graphs, graphs where every vertex has a sign + or −. The path graph Pk(G) of a graph G is obtained by representing the paths Pk in G by vertices whenever the corresponding paths Pk in G form a path Pk+1 or a cycle Ck. In this note, we introduce a natural extension of the notion of path graphs to the realm of signed graphs. It is shown that for any signed graph S, Pk(S) is balanced. The concept of a line signed graph is generalized to that of a path signed graphs. Further, in this note we discuss the structural characterization of path signed graphs. Also, we characterize signed graphs which are switching equivalent to their path signed graphs P3(S) (P4(S)).
- Signed graphs
- Line signed graphs
- Path signed graphs
- R. P. Abelson and M. J. Rosenberg, Symbolic psychologic: A model of attitudinal cognition, Behav. Sci., 3 (1958), 1-13.
- H. J. Broersma and C. Hoede, Path graphs, J. Graph Theory, 13 (1989), 427-444.
- M. K. Gill, Contributions to some topics in graph theory and its applications, Ph.D. thesis, The Indian Institute of Technology, Bombay, 1983.
- F. Harary, On the notion of balance of a sigraph, Michigan Math. J., 2(1953), 143-146.
- F. Harary, Structural duality, Behav. Sci., 2(4) (1957), 255-265.
- H. Li and Y. Lin, On the characterization of path graphs, J. Graph Theory, 17 (1993), 463-466.
- X. Li and B. Zhao, Isomorphisms of P4-graphs, Australas. J. Combin., 15 (1997), 135-143.
- E. Sampathkumar, Point signed and line signed graphs, Nat. Acad. Sci. Letters, 7(3) (1984), 91-93.
- E. Sampathkumar, P. Siva Kota Reddy, and M. S. Subramanya, The Line n-sigraph of a symmetric n-sigraph, Southeast Asian Bull. Math., to appear.
- E. Sampathkumar, M. S. Subramanya and P. Siva Kota Reddy, Characterization of Line Sidigraphs, Southeast Asian Bull. Math., to appear.
- D. B. West, Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd., 1996.
- T. Zaslavsky, Signed Graphs, Discrete Appl. Math., 4(1)(1982), 47-74.
Cite this paperAPA
Siva Kota Reddy, P. & Subramanya, M. S. (2009). Note on path signed graphs. Notes on Number Theory and Discrete Mathematics, 15(4), 1-6.Chicago
Siva Kota Reddy, P, and MS Subramanya. “Note on Path Signed Graphs.” Notes on Number Theory and Discrete Mathematics 15, no. 4 (2009): 1-6.MLA
Siva Kota Reddy, P, and MS Subramanya. “Note on Path Signed Graphs.” Notes on Number Theory and Discrete Mathematics 15.4 (2009): 1-6. Print.