Some graph mappings that preserve the sign of lambda2 −r

Applicable Analysis and Discrete Mathematics

article

Bojana Mihailović¹  Marija Rašajski¹ 

[1] School of Electrical Engineering, University of Belgrade

关键词: graph transformations;    spectral graph theory;    reflexive graph;    second largest eigenvalue;   

DOI  :  10.2298/AADM1701148M

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

In this article we deal with the sign of λ2 − r, r > 0, where λ2 is the secondlargest eigenvalue of (adjacency matrix of) a simple graph and present somemethods of determining it for some classes of graphs. The main result is aset of graph mappings that preserve the value of sgn (λ2 − r). These mappings induce equivalence relations among involved graphs, thus providing away to indirectly apply the GRS-theorem (the generalization of so-called RStheorem) to some GRS-undecidable (or RS-undecidable) graphs. To presentpossible applications, we revisit some of the previous results for reflexivegraphs (graphs whose second largest eigenvalue does not exceed 2). We showhow maximal reflexive graphs that belong to various families depending ontheir cyclic structure, can be reduced to RS-decidable graphs in terms ofcorresponding equivalence relations.

【 授权许可】

Unknown