On •-Line Signed Graphs L•(S)

Deepa Sinha; Ayushi Dhama

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 215-227
  • ISSN: 2083-5892

Abstract

top
A signed graph (or sigraph for short) is an ordered pair S = (Su,σ), where Su is a graph, G = (V,E), called the underlying graph of S and σ : E → {+,−} is a function from the edge set E of Su into the set {+,−}. For a sigraph S its •-line sigraph, L•(S) is the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such L-edge ee′ has the sign given by the product of the signs of the edges incident with the vertex in e ∩ e′. In this paper we establish a structural characterization of •-line sigraphs, extending a well known characterization of line graphs due to Harary. Further we study several standard properties of •-line sigraphs, such as the balanced •-line sigraphs, sign-compatible •-line sigraphs and C-sign-compatible •-line sigraphs.

How to cite

top

Deepa Sinha, and Ayushi Dhama. "On •-Line Signed Graphs L•(S)." Discussiones Mathematicae Graph Theory 35.2 (2015): 215-227. <http://eudml.org/doc/271091>.

@article{DeepaSinha2015,
abstract = {A signed graph (or sigraph for short) is an ordered pair S = (Su,σ), where Su is a graph, G = (V,E), called the underlying graph of S and σ : E → \{+,−\} is a function from the edge set E of Su into the set \{+,−\}. For a sigraph S its •-line sigraph, L•(S) is the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such L-edge ee′ has the sign given by the product of the signs of the edges incident with the vertex in e ∩ e′. In this paper we establish a structural characterization of •-line sigraphs, extending a well known characterization of line graphs due to Harary. Further we study several standard properties of •-line sigraphs, such as the balanced •-line sigraphs, sign-compatible •-line sigraphs and C-sign-compatible •-line sigraphs.},
author = {Deepa Sinha, Ayushi Dhama},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {sigraph; line graph; •-line sigraph; balance; sign-compatibility; C-sign-compatibility; -line sigraph; -sign-compatibility},
language = {eng},
number = {2},
pages = {215-227},
title = {On •-Line Signed Graphs L•(S)},
url = {http://eudml.org/doc/271091},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Deepa Sinha
AU - Ayushi Dhama
TI - On •-Line Signed Graphs L•(S)
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 215
EP - 227
AB - A signed graph (or sigraph for short) is an ordered pair S = (Su,σ), where Su is a graph, G = (V,E), called the underlying graph of S and σ : E → {+,−} is a function from the edge set E of Su into the set {+,−}. For a sigraph S its •-line sigraph, L•(S) is the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such L-edge ee′ has the sign given by the product of the signs of the edges incident with the vertex in e ∩ e′. In this paper we establish a structural characterization of •-line sigraphs, extending a well known characterization of line graphs due to Harary. Further we study several standard properties of •-line sigraphs, such as the balanced •-line sigraphs, sign-compatible •-line sigraphs and C-sign-compatible •-line sigraphs.
LA - eng
KW - sigraph; line graph; •-line sigraph; balance; sign-compatibility; C-sign-compatibility; -line sigraph; -sign-compatibility
UR - http://eudml.org/doc/271091
ER -

References

top
  1. [1] B.D. Acharya, Signed intersection graphs, J. Discrete Math. Sci. Cryptogr. 13 (2010) 553-569. doi:10.1080/09720529.2010.10698314[Crossref] Zbl1217.05170
  2. [2] M. Acharya and D. Sinha, Characterizations of line sigraphs, Nat. Acad. Sci. Lett. 28 (2005) 31-34. Extended abstract in: Electron. Notes Discrete Math. 15 (2003) 12. 
  3. [3] M. Behzad and G.T. Chartrand, Line coloring of signed graphs, Elem. Math. 24(3) (1969) 49-52. Zbl0175.50302
  4. [4] L.W. Beineke, Derived graphs and digraphs, in: Beitr¨age zur Graphentheorie, H. Sachs, H. Voss and H. Walter (Ed(s)), (Teubner, Leipzig, 1968) 17-33. Zbl0179.29204
  5. [5] L.W. Beineke, Characterizations of derived graphs, J. Combin. Theory (B) 9 (1970) 129-135. doi:10.1016/S0021-9800(70)80019-9[Crossref] 
  6. [6] M.K. Gill, Contribution to some topics in graph theory and its applications (Ph.D. Thesis, Indian Institute of Technology, Bombay, 1983). 
  7. [7] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953) 143-146. doi:10.1307/mmj/1028989917[Crossref] 
  8. [8] F. Harary, Graph Theory (Addison-Wesley Publ. Comp., Reading, Massachusetts, 1969). 
  9. [9] F. Harary and R.Z. Norman, Some properties of line digraphs, Rend. Circ. Mat. Palermo (2) Suppl. 9 (1960) 161-168. Zbl0099.18205
  10. [10] R.L. Hemminger and L.W. Beineke, Line graphs and line digraphs, in: Selected Topics in Graph Theory, L.W. Beineke and R.J. Wilson (Ed(s)), (Academic Press Inc., 1978) 271-305. 
  11. [11] J. Krausz, D´emonstration nouvelle d’une th´eor`eme de Whitney sur les r´eseaux , Mat. Fiz. Lapok 50 (1943) 75-89. 
  12. [12] V.V. Menon, On repeated interchange graphs, Amer. Math. Monthly 73 (1966) 986-989. doi:10.2307/2314503[Crossref] Zbl0144.45403
  13. [13] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, Providence, 1962). 
  14. [14] G. Sabidussi, Graph derivatives, Math. Z. 76 (1961) 385-401. doi:10.1007/BF01210984[Crossref] Zbl0109.16404
  15. [15] E. Sampathkumar, Point-signed and line-signed graphs, Karnatak Univ. Graph Theory Res. Rep. No.1 (1973) (also see Abstract No. 1 in: Graph Theory Newsletter 2(2) (1972), National Academy Science Letters 7 (1984) 91-93). 
  16. [16] D. Sinha, New frontiers in the theory of signed graph (Ph.D. Thesis, University of Delhi, Faculty of Technology, 2005). 
  17. [17] D. Sinha and A. Dhama, Sign-compatibility of some derived signed graphs, Indian J. Math. 55 (2013) 23-40. Zbl1274.05209
  18. [18] D. Sinha and A. Dhama, Canonical-sign-compatibility of some signed graphs, J. Combin. Inf. Syst. Sci. 38 (2013) 129-138. Zbl1316.05056
  19. [19] D.B. West, Introduction to Graph Theory (Prentice-Hall of India Pvt. Ltd., 1996). Zbl0845.05001
  20. [20] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168. doi:10.2307/2371086[Crossref] Zbl58.0609.01
  21. [21] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, 7th Edition, Electron. J. Combin. (1998) #DS8. Zbl0898.05001
  22. [22] T. Zaslavsky, Glossary of signed and gain graphs and allied areas, Second Edition, Electron. J. Combin. (1998) #DS9. Zbl0898.05002
  23. [23] T. Zaslavsky, Signed analogs of bipartite graphs, Discrete Math. 179 (1998) 205-216. doi:10.1016/S0012-365X(96)00386-X [Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.