Geodesic
On •-Line Signed Graphs L•(S)
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 215-227.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: sigraph, line graph, •-line sigraph, balance, sign-compatibility, C-sign-compatibility 
@article{DMGT_2015_35_2_a1,
     author = {Sinha, Deepa and Dhama, Ayushi},
     title = {On {{\textbullet}-Line} {Signed} {Graphs} {L\protect\textsubscript{{\textbullet}}(S)}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {215--227},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a1/}
}
TY  - JOUR
AU  - Sinha, Deepa
AU  - Dhama, Ayushi
TI  - On •-Line Signed Graphs L•(S)
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 215
EP  - 227
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a1/
LA  - en
ID  - DMGT_2015_35_2_a1
ER  - 
%0 Journal Article
%A Sinha, Deepa
%A Dhama, Ayushi
%T On •-Line Signed Graphs L•(S)
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 215-227
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a1/
%G en
%F DMGT_2015_35_2_a1
Sinha, Deepa; Dhama, Ayushi. On •-Line Signed Graphs L•(S). Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 215-227. http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a1/

[1] B.D. Acharya, Signed intersection graphs, J. Discrete Math. Sci. Cryptogr. 13 (2010) 553-569. doi:10.1080/09720529.2010.10698314

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

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

[5] L.W. Beineke, Characterizations of derived graphs, J. Combin. Theory (B) 9 (1970) 129-135. doi:10.1016/S0021-9800(70)80019-9

[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

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

[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émonstration nouvelle d’une théor`eme de Whitney sur les réseaux, 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

[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

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

[18] D. Sinha and A. Dhama, Canonical-sign-compatibility of some signed graphs, J. Combin. Inf. Syst. Sci. 38 (2013) 129-138.

[19] D.B. West, Introduction to Graph Theory (Prentice-Hall of India Pvt. Ltd., 1996).

[20] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168. doi:10.2307/2371086

[21] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, 7th Edition, Electron. J. Combin. (1998) #DS8.

[22] T. Zaslavsky, Glossary of signed and gain graphs and allied areas, Second Edition, Electron. J. Combin. (1998) #DS9.

[23] T. Zaslavsky, Signed analogs of bipartite graphs, Discrete Math. 179 (1998) 205-216. doi:10.1016/S0012-365X(96)00386-X