Geodesic
Signed Complete Graphs with Maximum Index
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 393-403.

Voir la notice de l'article provenant de la source Library of Science

Let Γ = (G, σ) be a signed graph, where G is the underlying simple graph and σ E(G) → −, + is the sign function on the edges of G. The adjacency matrix of a signed graph has −1 or +1 for adjacent vertices, depending on the sign of the edges. It was conjectured that if is a signed complete graph of order n with k negative edges, k lt; n − 1 and has maximum index, then negative edges form K1,k. In this paper, we prove this conjecture if we confine ourselves to all signed complete graphs of order n whose negative edges form a tree of order k + 1. A [1, 2]-subgraph of G is a graph whose components are paths and cycles. Let Γ be a signed complete graph whose negative edges form a [1, 2]-subgraph. We show that the eigenvalues of Γ satisfy the following inequalities: −5 ≤ λn ≤ . . . ≤ λ2 ≤ 3.
Keywords: signed graph, complete graph, index 
@article{DMGT_2020_40_2_a2,
     author = {Akbari, Saieed and Dalvandi, Soudabeh and Heydari, Farideh and Maghasedi, Mohammad},
     title = {Signed {Complete} {Graphs} with {Maximum} {Index}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {393--403},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a2/}
}
TY  - JOUR
AU  - Akbari, Saieed
AU  - Dalvandi, Soudabeh
AU  - Heydari, Farideh
AU  - Maghasedi, Mohammad
TI  - Signed Complete Graphs with Maximum Index
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 393
EP  - 403
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a2/
LA  - en
ID  - DMGT_2020_40_2_a2
ER  - 
%0 Journal Article
%A Akbari, Saieed
%A Dalvandi, Soudabeh
%A Heydari, Farideh
%A Maghasedi, Mohammad
%T Signed Complete Graphs with Maximum Index
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 393-403
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a2/
%G en
%F DMGT_2020_40_2_a2
Akbari, Saieed; Dalvandi, Soudabeh; Heydari, Farideh; Maghasedi, Mohammad. Signed Complete Graphs with Maximum Index. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 393-403. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a2/

[1] N. Abreu, D.M. Cardoso, F.A.M. Franca and C.T.M. Vinagre, On main eigenvalues of certain graphs, Comput. Appl. Math., to appear.

[2] S. Akbari, S. Dalvandi, F. Heydari and M. Maghasedi, On the eigenvalues of signed complete graphs, Linear Multilinear Algebra 67 (2019) 433–441. doi:10.1080/03081087.2017.1403548

[3] S. Akbari, S. Dalvandi, F. Heydari and M. Maghasedi, On the multiplicity of − 1 and 1 in signed complete graphs, Util. Math., to appear.

[4] F. Belardo, P. Petecki and J. Wang, On signed graphs whose second largest Laplacian eigenvalue does not exceed 3, Linear Multilinear Algebra 64 (2016) 1785–1799. doi:10.1080/03081087.2015.1120701

[5] A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, 2011). doi:10.1007/978-1-4614-1939-6

[6] D. Cvetković, P. Rowlinson and S.K. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2010).

[7] F. Harary, On the notion of balance in a signed graph, Michigan Math. J. 2 (1953) 143–146. doi:10.1307/mmj/1028989917

[8] F. Heider, Attitude and cognitive organization, J. Psychology 21 (1946) 107–112. doi:10.1080/00223980.1946.9917275

[9] T. Koledin and Z. Stanić, Connected signed graphs of fixed order, size, and number of negative edges with maximal index, Linear Multilinear Algebra 65 (2017) 2187–2198. doi:10.1080/03081087.2016.1265480

[10] H. Lin, R. Liu and J. Shu, Some results on the largest and least eigenvalues of graphs, Electron. J. Linear Algebra 27 (2014) 670–682. doi:/10.13001/1081-3810.1928

[11] S.M. Lv, L. Wei and H.X. Zhao, On the Seidel integral complete multipartite graphs, Acta Math. Appl. Sin. Engl. Ser. 28 (2012) 705–710. doi:10.1007/s10255-012-0126-x

[12] Z. Stanić, Perturbations in a signed graph and its index, Discuss. Math. Graph Theory 38 (2018) 841–852. doi:10.7151/dmgt.2035