Signed graphs with maximal index

被引：13
作者：
Ghorbani, Ebrahim [1 ,2 ]
Majidi, Arezoo [1 ]
机构：
[1] KN Toosi Univ Technol, Dept Math, POB 16765-3381, Tehran, Iran
[2] Univ Hamburg, Dept Math, Bundesstr 55 Geomatikum, D-20146 Hamburg, Germany
来源：
DISCRETE MATHEMATICS | 2021年 / 344卷 / 08期
关键词：
Signed graph; Index; Seidel matrix; Spectral radius;
D O I：
10.1016/j.disc.2021.112463
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The index of a signed graph is the largest eigenvalue of its adjacency matrix. For positive integers nand m <= n(2)/4, we determine the maximum index of complete signed graphs with n vertices and m negative edges and characterize the signed graphs achieving this maximum. This settles (the corrected version of) a conjecture by Koledin and Stanic (2017). (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数：8
相关论文
共 7 条
[1]   SIGNED COMPLETE GRAPHS WITH MAXIMUM INDEX [J].
Akbari, Saieed ;
Dalvandi, Soudabeh ;
Heydari, Farideh ;
Maghasedi, Mohammad .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2020, 40 (02) :393-403
[2]  
Belardo F., 2018, ART DISCRETE APPL MA, V1
[3]   Lifts, discrepancy and nearly optimal spectral cap [J].
Bilu, Yonatan ;
Linial, Nathan .
COMBINATORICA, 2006, 26 (05) :495-519
[4]  
Brouwer AE, 2012, UNIVERSITEXT, P1, DOI 10.1007/978-1-4614-1939-6
[5]   Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture [J].
Huang, Hao .
ANNALS OF MATHEMATICS, 2019, 190 (03) :949-955
[6]   Connected signed graphs of fixed order, size, and number of negative edges with maximal index [J].
Koledin, Tamara ;
Stanic, Zoran .
LINEAR & MULTILINEAR ALGEBRA, 2017, 65 (11) :2187-2198
[7]   Interlacing families I: Bipartite Ramanujan graphs of all degrees [J].
Marcus, Adam W. ;
Spielman, Daniel A. ;
Srivastava, Nikhil .
ANNALS OF MATHEMATICS, 2015, 182 (01) :307-325
1