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.
@article{bwmeta1.element.doi-10_7151_dmgt_1793,
author = {Deepa Sinha and Ayushi Dhama},
title = {On $\bullet$-Line Signed Graphs L$\bullet$(S)},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {215-227},
zbl = {1311.05078},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1793}
}
Deepa Sinha; Ayushi Dhama. On •-Line Signed Graphs L•(S). Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 215-227. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1793/
[1] B.D. Acharya, Signed intersection graphs, J. Discrete Math. Sci. Cryptogr. 13 (2010) 553-569. doi:10.1080/09720529.2010.10698314[Crossref] | Zbl 1217.05170
[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] M. Behzad and G.T. Chartrand, Line coloring of signed graphs, Elem. Math. 24(3) (1969) 49-52. | Zbl 0175.50302
[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. | Zbl 0179.29204
[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] M.K. Gill, Contribution to some topics in graph theory and its applications (Ph.D. Thesis, Indian Institute of Technology, Bombay, 1983).
[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] F. Harary, Graph Theory (Addison-Wesley Publ. Comp., Reading, Massachusetts, 1969).
[9] F. Harary and R.Z. Norman, Some properties of line digraphs, Rend. Circ. Mat. Palermo (2) Suppl. 9 (1960) 161-168. | Zbl 0099.18205
[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] J. Krausz, D´emonstration nouvelle d’une th´eor`eme de Whitney sur les r´eseaux , Mat. Fiz. Lapok 50 (1943) 75-89.
[12] V.V. Menon, On repeated interchange graphs, Amer. Math. Monthly 73 (1966) 986-989. doi:10.2307/2314503[Crossref] | Zbl 0144.45403
[13] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, Providence, 1962).
[14] G. Sabidussi, Graph derivatives, Math. Z. 76 (1961) 385-401. doi:10.1007/BF01210984[Crossref] | Zbl 0109.16404
[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] D. Sinha, New frontiers in the theory of signed graph (Ph.D. Thesis, University of Delhi, Faculty of Technology, 2005).
[17] D. Sinha and A. Dhama, Sign-compatibility of some derived signed graphs, Indian J. Math. 55 (2013) 23-40. | Zbl 1274.05209
[18] D. Sinha and A. Dhama, Canonical-sign-compatibility of some signed graphs, J. Combin. Inf. Syst. Sci. 38 (2013) 129-138. | Zbl 1316.05056
[19] D.B. West, Introduction to Graph Theory (Prentice-Hall of India Pvt. Ltd., 1996). | Zbl 0845.05001
[20] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168. doi:10.2307/2371086[Crossref] | Zbl 58.0609.01
[21] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, 7th Edition, Electron. J. Combin. (1998) #DS8. | Zbl 0898.05001
[22] T. Zaslavsky, Glossary of signed and gain graphs and allied areas, Second Edition, Electron. J. Combin. (1998) #DS9. | Zbl 0898.05002
[23] T. Zaslavsky, Signed analogs of bipartite graphs, Discrete Math. 179 (1998) 205-216. doi:10.1016/S0012-365X(96)00386-X [Crossref]