Note on path signed graphs

P. Siva Kota Reddy and M. S. Subramanya
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 15, 2009, Number 4, Pages 1–6
Full paper (PDF, 129 Kb)

Details

Authors and affiliations

P. Siva Kota Reddy
Department of Studies in Mathematics
University of Mysore, Manasagangotri
Mysore 570 006, India

M. S. Subramanya
Department of Studies in Mathematics
University of Mysore, Manasagangotri
Mysore 570 006, India

Abstract

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

Keywords

  • Signed graphs
  • Balance
  • Switching
  • Line signed graphs
  • Path signed graphs
  • Negation

AMS Classification

  • 05C22

References

  1. R. P. Abelson and M. J. Rosenberg, Symbolic psychologic: A model of attitudinal cognition, Behav. Sci., 3 (1958), 1-13.
  2. H. J. Broersma and C. Hoede, Path graphs, J. Graph Theory, 13 (1989), 427-444.
  3. M. K. Gill, Contributions to some topics in graph theory and its applications, Ph.D. thesis, The Indian Institute of Technology, Bombay, 1983.
  4. F. Harary, On the notion of balance of a sigraph, Michigan Math. J., 2(1953), 143-146.
  5. F. Harary, Structural duality, Behav. Sci., 2(4) (1957), 255-265.
  6. H. Li and Y. Lin, On the characterization of path graphs, J. Graph Theory, 17 (1993), 463-466.
  7. X. Li and B. Zhao, Isomorphisms of P4-graphs, Australas. J. Combin., 15 (1997), 135-143.
  8. E. Sampathkumar, Point signed and line signed graphs, Nat. Acad. Sci. Letters, 7(3) (1984), 91-93.
  9. 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.
  10. E. Sampathkumar, M. S. Subramanya and P. Siva Kota Reddy, Characterization of Line Sidigraphs, Southeast Asian Bull. Math., to appear.
  11. D. B. West, Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd., 1996.
  12. T. Zaslavsky, Signed Graphs, Discrete Appl. Math., 4(1)(1982), 47-74.

Related papers

Cite this paper

Siva Kota Reddy, P., & Subramanya, M. S. (2009). Note on path signed graphs. Notes on Number Theory and Discrete Mathematics, 15(4), 1-6.

Comments are closed.