On •-Line Signed Graphs L•(S)

• Autorzy: Deepa Sinha , Ayushi Dhama
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

sigraph; line graph; •-line sigraph; balance; sign-compatibility; C-sign-compatibility

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 2
• Strony: 215-227

Daty

wydano

2015-05-01

otrzymano

2013-09-25

poprawiono

2014-04-07

zaakceptowano

2014-04-09

online

2015-04-18

Twórcy

autor

Deepa Sinha

• South Asian University Akbar Bhawan, Chanakyapuri New Delhi-110 021, India

autor

Ayushi Dhama

• Centre for Mathematical Sciences Banasthali University Banasthali-304 022 Rajasthan, India

Bibliografia

• [1] B.D. Acharya, Signed intersection graphs, J. Discrete Math. Sci. Cryptogr. 13 (2010) 553-569. doi:10.1080/09720529.2010.10698314[Crossref]
• [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[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.
• [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]
• [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]
• [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[Crossref]
• [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 [Crossref]

Identyfikatory

DOI

10.7151/dmgt.1793