Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/1375
Title: Notes on upper bounds for the largest eigenvalue based on edge-decompositions of a signed graph
Authors: Stanić, Zoran 
Keywords: Adjacency matrix;Decomposition;Eulerian signed graph;Hamiltonian signed graph;Largest eigenvalue
Issue Date: 1-Jul-2023
Rank: M23
Publisher: Elsevier
Journal: Kuwait Journal of Science
Abstract: 
The adjacency matrix of a signed graph has +1 or −1 for adjacent vertices, depending on the sign of the connecting edge. According to this concept, an ordinary graph can be interpreted as a signed graph without negative edges. An edge-decomposition of a signed graph Ġ is a partition of its edge set into (non-empty) subsets E1, E2, …, Ek. Every subset Ei (1 ​≤ ​i ​≤ ​k) induces a subgraph of Ġ obtained by keeping only the edges of Ei. Accordingly, a fixed edge-decomposition induces a decomposition of Ġ into the corresponding subgraphs. This paper establishes some upper bounds for the largest eigenvalue of the adjacency matrix of a signed graph Ġ expressed in terms of the largest eigenvalues of subgraphs induced by edge-decompositions. A particular attention is devoted to the so-called cycle decompositions, i.e., decompositions into signed cycles. It is proved that Ġ has a cycle decomposition if and only if it is Eulerian. The upper bounds for the largest eigenvalue in terms of the largest eigenvalues of the corresponding cycles are obtained for regular signed graphs and Hamiltonian signed graphs. These bounds are interesting since all of them can easily be computed, as the largest eigenvalue of a signed cycle is equal to 2 if the product of its edge signs is positive, while otherwise it is 2cos[Formula presented], where j stands for the length. Several examples are provided. The entire paper is related to some classical results in which the same approach is applied to ordinary graphs.
URI: https://research.matf.bg.ac.rs/handle/123456789/1375
ISSN: 23074108
DOI: 10.1016/j.kjs.2023.05.003
Rights: Attribution-NonCommercial-NoDerivs 3.0 United States
Appears in Collections:Research outputs

Files in This Item:
File Description SizeFormat
1-s2.0-S2307410823000421-main.pdf292.22 kBAdobe PDF
View/Open
Show full item record

Page view(s)

13
checked on Dec 24, 2024

Download(s)

1
checked on Dec 24, 2024

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons