On composition of signed graphs

K. Shahul Hameed; K.A. Germina

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 3, page 507-516
  • ISSN: 2083-5892

Abstract

top
A graph whose edges are labeled either as positive or negative is called a signed graph. In this article, we extend the notion of composition of (unsigned) graphs (also called lexicographic product) to signed graphs. We employ Kronecker product of matrices to express the adjacency matrix of this product of two signed graphs and hence find its eigenvalues when the second graph under composition is net-regular. A signed graph is said to be net-regular if every vertex has constant net-degree, namely, the difference of the number of positive and negative edges incident with a vertex. We also characterize balance in signed graph composition and have some results on the Laplacian matrices of this product.

How to cite

top

K. Shahul Hameed, and K.A. Germina. "On composition of signed graphs." Discussiones Mathematicae Graph Theory 32.3 (2012): 507-516. <http://eudml.org/doc/270991>.

@article{K2012,
abstract = {A graph whose edges are labeled either as positive or negative is called a signed graph. In this article, we extend the notion of composition of (unsigned) graphs (also called lexicographic product) to signed graphs. We employ Kronecker product of matrices to express the adjacency matrix of this product of two signed graphs and hence find its eigenvalues when the second graph under composition is net-regular. A signed graph is said to be net-regular if every vertex has constant net-degree, namely, the difference of the number of positive and negative edges incident with a vertex. We also characterize balance in signed graph composition and have some results on the Laplacian matrices of this product.},
author = {K. Shahul Hameed, K.A. Germina},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {signed graph; eigenvalues; graph composition; regular graphs; net-regular signed graphs},
language = {eng},
number = {3},
pages = {507-516},
title = {On composition of signed graphs},
url = {http://eudml.org/doc/270991},
volume = {32},
year = {2012},
}

TY - JOUR
AU - K. Shahul Hameed
AU - K.A. Germina
TI - On composition of signed graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 3
SP - 507
EP - 516
AB - A graph whose edges are labeled either as positive or negative is called a signed graph. In this article, we extend the notion of composition of (unsigned) graphs (also called lexicographic product) to signed graphs. We employ Kronecker product of matrices to express the adjacency matrix of this product of two signed graphs and hence find its eigenvalues when the second graph under composition is net-regular. A signed graph is said to be net-regular if every vertex has constant net-degree, namely, the difference of the number of positive and negative edges incident with a vertex. We also characterize balance in signed graph composition and have some results on the Laplacian matrices of this product.
LA - eng
KW - signed graph; eigenvalues; graph composition; regular graphs; net-regular signed graphs
UR - http://eudml.org/doc/270991
ER -

References

top
  1. [1] B.D. Acharya, Spectral criterion for cycle balance in networks, J. Graph Theory 4 (1980) 1-11, doi: 10.1002/jgt.3190040102. Zbl0445.05066
  2. [2] F. Barahona, On the computational complexity of Ising spin glass models, J. Phys. (A) 15 (1982) 3241-3253, doi: 10.1088/0305-4470/15/10/028. 
  3. [3] D. Cartwright and F. Harary, Structural balance: a generalization of Heider?s theory, Psychological Rev. 63 (1956) 277-293, doi: 10.1037/h0046049. 
  4. [4] G. Chartrand, H. Gavlas, F. Harary and M. Schultz, On signed degrees in signed graphs, Czechoslovak Math. J. 44 (1994) 677-680. Zbl0837.05110
  5. [5] D.M. Cvetkovi'c, M. Doob and H. Sachs, Spectra of Graphs (third ed., Johann Abrosius Barth Verlag, 1995). 
  6. [6] F. Harary, Graph Theory ( Addison Wesley, Reading, MA, 1972). 
  7. [7] K.A. Germina and K. Shahul Hameed, On signed paths, signed cycles and their energies, Applied Math. Sci. 70 (2010) 3455-3466, doi: 10.1016/j.laa.2010.10.026. Zbl1237.05125
  8. [8] K.A. Germina, K. Shahul Hameed and T. Zaslavsky, On product and line graphs of signed graphs, their eigenvalues and energy, Linear Algebra Appl. 435 (2011) 2432-2450, doi: 10.1007/s10587-007-0079-z. Zbl1222.05223
  9. [9] S. Pirzada, T.A. Naikoo and F.A. Dar, Signed degree sets in signed graphs, Czechoslovak Math. J. 57 (2007) 843-848, doi: 10.1215/S0012-7094-59-02667-5. Zbl1174.05059
  10. [10] S. Pirzada, T.A. Naikoo and F.A. Dar, Signed degree sets in signed bipartite graphs, AKCE Int. J. Graphs and Combin. 4(3) (2007) 301-312. Zbl1143.05307
  11. [11] G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693-696, doi: 10.1215/S0012-7094-59-02667-5. Zbl0095.37802
  12. [12] G. Sabidussi, The lexicographic product of graphs, Duke Math. J. 28 (1961) 573-578, doi: 10.1215/S0012-7094-61-02857-5. Zbl0115.41102
  13. [13] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982) 47-74, Erratum: Discrete Appl. Math. 5 (1983) 248-248, doi: 10.1016/0166-218X(83)90047-1. Zbl0476.05080
  14. [14] T. Zaslavsky, Matrices in the theory of signed simple. Zbl1231.05120
  15. [15] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, VII Edition, Electronic J. Combin. 8 (1998), Dynamic Surveys: #8. Zbl0898.05001
  16. [16] F. Zhang, Matrix Theory: Basic Theory and Techniques ( Springer-Verlag, 1999). Zbl0948.15001

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.