Characterization of Line-Consistent Signed Graphs

Daniel C. Slilaty; Thomas Zaslavsky

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 3, page 589-594
  • ISSN: 2083-5892

Abstract

top
The line graph of a graph with signed edges carries vertex signs. A vertex-signed graph is consistent if every circle (cycle, circuit) has positive vertex-sign product. Acharya, Acharya, and Sinha recently characterized line-consistent signed graphs, i.e., edge-signed graphs whose line graphs, with the naturally induced vertex signature, are consistent. Their proof applies Hoede’s relatively difficult characterization of consistent vertex-signed graphs. We give a simple proof that does not depend on Hoede’s theorem as well as a structural description of line-consistent signed graphs.

How to cite

top

Daniel C. Slilaty, and Thomas Zaslavsky. "Characterization of Line-Consistent Signed Graphs." Discussiones Mathematicae Graph Theory 35.3 (2015): 589-594. <http://eudml.org/doc/271218>.

@article{DanielC2015,
abstract = {The line graph of a graph with signed edges carries vertex signs. A vertex-signed graph is consistent if every circle (cycle, circuit) has positive vertex-sign product. Acharya, Acharya, and Sinha recently characterized line-consistent signed graphs, i.e., edge-signed graphs whose line graphs, with the naturally induced vertex signature, are consistent. Their proof applies Hoede’s relatively difficult characterization of consistent vertex-signed graphs. We give a simple proof that does not depend on Hoede’s theorem as well as a structural description of line-consistent signed graphs.},
author = {Daniel C. Slilaty, Thomas Zaslavsky},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {line-consistent signed graph; line graph; consistent vertex-signed graph; consistent marked graph.; consistent marked graph},
language = {eng},
number = {3},
pages = {589-594},
title = {Characterization of Line-Consistent Signed Graphs},
url = {http://eudml.org/doc/271218},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Daniel C. Slilaty
AU - Thomas Zaslavsky
TI - Characterization of Line-Consistent Signed Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 3
SP - 589
EP - 594
AB - The line graph of a graph with signed edges carries vertex signs. A vertex-signed graph is consistent if every circle (cycle, circuit) has positive vertex-sign product. Acharya, Acharya, and Sinha recently characterized line-consistent signed graphs, i.e., edge-signed graphs whose line graphs, with the naturally induced vertex signature, are consistent. Their proof applies Hoede’s relatively difficult characterization of consistent vertex-signed graphs. We give a simple proof that does not depend on Hoede’s theorem as well as a structural description of line-consistent signed graphs.
LA - eng
KW - line-consistent signed graph; line graph; consistent vertex-signed graph; consistent marked graph.; consistent marked graph
UR - http://eudml.org/doc/271218
ER -

References

top
  1. [1] B.D. Acharya, A characterization of consistent marked graphs, Nat. Acad. Sci. Let- ters (India) 6 (1983) 431-440. Zbl0552.05052
  2. [2] B.D. Acharya, Some further properties of consistent marked graphs, Indian J. Pure Appl. Math. 15 (1984) 837-842. Zbl0552.05053
  3. [3] B.D. Acharya, M. Acharya and D. Sinha, Cycle-compatible signed line graphs, Indian J. Math. 50 (2008) 407-414. Zbl1170.05032
  4. [4] B.D. Acharya, M. Acharya and D. Sinha, Characterization of a signed graph whose signed line graph is S-consistent , Bull. Malaysian Math. Sci. Soc. (2) 32 (2009) 335-341. Zbl1176.05032
  5. [5] M. Acharya, ×-line signed graphs, J. Combin. Math. Combin. Comput. 69 (2009) 103-111. Zbl1195.05031
  6. [6] M. Behzad and G. Chartrand, Line-coloring of signed graphs, Elem. Math. 24 (1969) 49-52. Zbl0175.50302
  7. [7] L.W. Beineke and F. Harary, Consistent graphs with signed points, Riv. Mat. Sci. Econom. Social. 1 (1978) 81-88. doi:10.1002/jgt.3190160104[Crossref] Zbl0493.05053
  8. [8] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953-54) 143-146 and addendum preceding p. 1. 
  9. [9] C. Hoede, A characterization of consistent marked graphs, J. Graph Theory 16 (1992) 17-23. doi:10.1002/jgt.3190160104[Crossref] 
  10. [10] M. Joglekar, N. Shah and A.A. Diwan, Balanced group labeled graphs, Discrete Math. 312 (2012) 1542-1549. doi:10.1016/j.disc.2011.09.021[WoS][Crossref] Zbl1239.05162
  11. [11] S.B. Rao, Characterizations of harmonious marked graphs and consistent nets, J. Comb. Inf. Syst. Sci. 9 (1984) 97-112. Zbl0625.05049
  12. [12] F.S. Roberts and S. Xu, Characterizations of consistent marked graphs, Discrete Appl. Math. 127 (2003) 357-371. doi:10.1016/S0166-218X(02)00254-8[Crossref] Zbl1026.05054
  13. [13] T. Zaslavsky, Matrices in the theory of signed simple graphs, Advances in Discrete Mathematics and Applications: Mysore, 2008, B.D. Acharya, G.O.H. Katona, and J. Nesetril, Eds., Ramanujan Math. Soc., Mysore, India (2010) 207-229. 
  14. [14] T. Zaslavsky, Consistency in the naturally vertex-signed line graph of a signed graph, Bull. Malaysian Math. Sci. Soc., to appear. 

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.