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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1615,
author = {K. Shahul Hameed and K.A. Germina},
title = {On composition of signed graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {507-516},
zbl = {1257.05056},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1615}
}
K. Shahul Hameed; K.A. Germina. On composition of signed graphs. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 507-516. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1615/
[000] [1] B.D. Acharya, Spectral criterion for cycle balance in networks, J. Graph Theory 4 (1980) 1-11, doi: 10.1002/jgt.3190040102. | Zbl 0445.05066
[001] [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.
[002] [3] D. Cartwright and F. Harary, Structural balance: a generalization of Heider?s theory, Psychological Rev. 63 (1956) 277-293, doi: 10.1037/h0046049.
[003] [4] G. Chartrand, H. Gavlas, F. Harary and M. Schultz, On signed degrees in signed graphs, Czechoslovak Math. J. 44 (1994) 677-680. | Zbl 0837.05110
[004] [5] D.M. Cvetkovi'c, M. Doob and H. Sachs, Spectra of Graphs (third ed., Johann Abrosius Barth Verlag, 1995).
[005] [6] F. Harary, Graph Theory ( Addison Wesley, Reading, MA, 1972).
[006] [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. | Zbl 1237.05125
[007] [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. | Zbl 1222.05223
[008] [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. | Zbl 1174.05059
[009] [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. | Zbl 1143.05307
[010] [11] G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693-696, doi: 10.1215/S0012-7094-59-02667-5. | Zbl 0095.37802
[011] [12] G. Sabidussi, The lexicographic product of graphs, Duke Math. J. 28 (1961) 573-578, doi: 10.1215/S0012-7094-61-02857-5. | Zbl 0115.41102
[012] [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. | Zbl 0476.05080
[013] [14] T. Zaslavsky, Matrices in the theory of signed simple. | Zbl 1231.05120
[014] [15] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, VII Edition, Electronic J. Combin. 8 (1998), Dynamic Surveys: #8. | Zbl 0898.05001
[015] [16] F. Zhang, Matrix Theory: Basic Theory and Techniques ( Springer-Verlag, 1999). | Zbl 0948.15001