Restricted super line signed graph RL_r(S)

P. Siva Kota Reddy and U. K. Misra
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 19, 2013, Number 4, Pages 86–92
Full paper (PDF, 178 Kb)

Details

Authors and affiliations

P. Siva Kota Reddy
Department of Mathematics
Siddaganga Institute of Technology
B. H. Road, Tumkur–572 103, India

U. K. Misra
Department of Mathematics
Berhampur University
Berhampur–760 007, Orissa, India

Abstract

A signed graph (marked graph) is an ordered pair S = (G; σ) (S = (G; μ)), where G = (V, E) is a graph called the underlying graph of S and σ : E → {+, −} (μ : V → {+, −}) is a function. The restricted super line graph of index r of a graph G, denoted by RL_r(G). The vertices of RLr(G) are the r-subsets of E(G) and two vertices P = {p₁, p₂ …, p_r} and Q = {q₁, q₂ …, q_r} are adjacent if there exists exactly one pair of edges, say p_i and q_j , where 1 ≤ i; j ≤ r, that are adjacent edges in G.
Analogously, one can define the restricted super line signed graph of index r of a signed graph S = (G; σ) as a signed graph RLr(S) = (RLr(G); σ′), where RLr(G) is the underlying graph of RLr(S), where for any edge PQ in RLr(S), σ′(PQ) = σ(P)σ(Q). It is shown that for any signed graph S, its RLr(S) is balanced and we offer a structural characterization of restricted super line signed graphs of index r.
Further, we characterize signed graphs S for which RLr(S) ~ Lr(S) and RLr(S) ≅ Lr(S), where ~ and ≅ denote switching equivalence and isomorphism and RLr(S) and Lr(S) are denotes the restricted super line signed graph of index r and super line signed graph of index r of S, respectively.

Keywords

• Signed graphs
• Marked graphs
• Balance
• Switching
• Restricted super line signed graph
• Super line signed graphs
• Negation

AMS Classification

• 05C22

References

1. Abelson, R. P., M. J. Rosenberg, Symbolic psychologic: A model of attitudinal cognition, Behav. Sci., Vol. 3, 1958, 1–13.
2. Bagga, K. S., L. W. Beineke, B. N. Varma, Super line graphs, In: Y. Alavi, A. Schwenk (Eds.), Graph Theory, Combinatorics and Applications, Wiley-Interscience, New York, Vol. 1, 1995, 35–46.
3. Bagga, K. S., L. W. Beineke, B. N. Varma, The super line graph L₂(G), Discrete Math., Vol. 206, 1999, 51–61.
4. Cartwright, D. W., F. Harary, Structural balance: A generalization of Heider’s Theory, Psych. Rev., Vol. 63, 1956, 277–293.
5. Chartrand, G. T. Graphs as Mathematical Models, Prindle, Weber & Schmidt, Inc., Boston, Massachusetts, 1977.
6. Gill, M. K. Contributions to some topics in graph theory and its applications, Ph.D. thesis, The Indian Institute of Technology, Bombay, 1983.
7. Harary, F. Graph Theory, Addison-Wesley Publishing Co., 1969.
8. Harary, F. On the notion of balance of a signed graph, Michigan Math. J., Vol. 2, 1953, 143–146.
9. Harary, F. Structural duality, Behav. Sci., Vol. 2, 1957, No. 4, 255–265.
10. Harary, F., R. Z. Norman, D. W. Cartwright, Structural models: An introduction to the theory of directed graphs, Wiley Inter-Science, Inc., New York, 1965.
11. Harary, F., J. A. Kabell, Counting balanced signed graphs using marked graphs, Proc. Edinburgh Math. Soc., Vol. 24, 1981, No. 2, 99–104.
12. Katai, O., S. Iwai, Studies on the balancing, the minimal balancing, and the minimum balancing processes for social groups with planar and nonplanar graph structures, J. Math. Psychol., Vol. 18, 1978, 140–176.
13. Manjula, K. Some results on generalized line graphs, Ph.D. thesis, Bangalore University, Bangalore, 2004.
14. Rangarajan, R., P. S. K. Reddy, The edge C₄ signed graph of a signed graph, Southeast Asain Bull. Math., Vol. 34, 2010, No. 6, 1077–1082.
15. Roberts, F. S. Graph Theory and its Applications to Problems of Society, SIAM, Philadelphia, PA, USA, 1978.
16. Roberts, F. S., Shaoji Xu, Characterizations of consistent marked graphs, Discrete Applied Mathematics, Vol. 127, 2003, 357–371.
17. Sampathkumar, E. Point signed and line signed graphs, Nat. Acad. Sci. Letters, Vol. 7, 1984, No. 3, 91–93.
18. Sampathkumar, E., P. S. K. Reddy, M. S. Subramanya, Directionally n-signed graphs, Ramanujan Math. Soc., Lecture Notes Series (Proc. Int. Conf. ICDM 2008), Vol. 13, 2010, 155–162.
19. Sampathkumar, E., P. S. K. Reddy, M. S. Subramanya, Directionally n-signed graphs-II, International J. Math. Combin., Vol. 4, 2009, 89–98.
20. Sampathkumar, E., P. S. K. Reddy, M. S. Subramanya, The Line n-sigraph of a symmetric n-sigraph, Southeast Asian Bull. Math., Vol. 34, 2010, No. 5, 953–958.
21. Sampathkumar, E., M. S. Subramanya, P. S. K. Reddy, Characterization of line sidigraphs, Southeast Asian Bull. Math., Vol. 35, 2011, No. 2, 297–304.
22. Reddy, P. S. K., M. S. Subramanya. Note on Path Signed Graphs. Notes on Number Theory and Discrete Mathematics, Vol. 15, 2009, No. 4, 1–6.
23. Reddy, P. S. K., E. Sampathkumar, M. S. Subramanya, Common-edge signed graph of a signed graph, J. Indones. Math. Soc., Vol. 16, 2010, No. 2, 105–112.
24. Reddy, P. S. K. t-Path Sigraphs, Tamsui Oxford J. of Math. Sciences, Vol. 26, 2010, No. 4, 433–441.
25. Reddy, P. S. K., R. Rangarajan, M. S. Subramanya, Switching invariant Neighborhood signed graphs, Proceedings of the Jangjeon Math. Soc., Vol. 14, 2011, No. 2, 249–258.
26. Reddy, P. S. K., S. Vijay, The super line signed graph L_r(S )of a signed graph, Southeast Asian Bull. Math., Vol. 36, 2012, No. 6, 875–882.
27. Reddy, P. S. K., U. K. Misra. Common Minimal Equitable Dominating Signed Graphs. Notes on Number Theory and Discrete Mathematics, Vol. 18, 2012, No. 4, 40–46.
28. Reddy, P. S. K., B. Prashanth, The common minimal dominating signed graph, Transactions on Combinatorics, Vol. 1, 2012, No. 3, 39–46.
29. Reddy, P. S. K., U. K. Misra, The Equitable Associate Signed Graphs, Bull. Int. Math. Virtual Inst., Vol. 3, 2013m No. 1, 15–20.
30. Reddy, P. S. K., K. R. Rajanna, Kavita S. Permi. The Common Minimal Common Neighborhood Dominating Signed Graphs, Transactions on Combinatorics, Vol. 2, 2013, No. 1, 1–8.
31. Reddy, P. S. K. Smarandache Directionally n-Signed Graphs: A Survey, International J. Math. Combin., Vol. 2, 2013, 34–43.
32. Reddy, P. S. K., U. K. Misra, Graphoidal Signed Graphs, Advn. Stud. Contemp. Math., Vol. 23, 2013, No. 3, 451–460.
33. Reddy, P. S. K., U. K. Misra, Directionally n-signed graphs-III: The notion of symmetric balance, Transactions on Combinatorics, Vol. 2, 2013, No. 4, 53–62.
34. Sozánsky, T. Enumeration of weak isomorphism classes of signed graphs, J. Graph Theory, Vol. 4, 1980, No. 2 127–144.
35. Zaslavsky, T. Signed Graphs, Discrete Appl. Math., Vol. 4, 1982, No. 1, 47–74.
36. Zaslavsky, T. A mathematical bibliography of signed and gain graphs and its allied areas, Electronic J. Combin., Vol. 8, 1998, No. 1, Dynamic Surveys, 1999, No. DS8.