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.