Notes on upper bounds for the largest eigenvalue based on edge-decompositions of a signed graph
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 G is a partition of its edge set...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2023-07-01
|
| Series: | Kuwait Journal of Science |
| Subjects: | |
| Online Access: | https://www.sciencedirect.com/science/article/pii/S2307410823000421 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 G is a partition of its edge set into (non-empty) subsets E1, E2, ..., Ek. Every subset Ei (1 ≤ i ≤ k) induces a subgraph of G obtained by keeping only the edges of Ei. Accordingly, a fixed edge-decomposition induces a decomposition of G into the corresponding subgraphs. This paper establishes some upper bounds for the largest eigenvalue of the adjacency matrix of a signed graph G, expressed in terms of the largest eigenvalues of subgraphs induced by edge-decompositions. Special attention is given to cycle decompositions, i.e., decompositions into signed cycles. It is proved that G 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 because all of them can easily be computed. The largest eigenvalue of a signed cycle is equal to 2 if the product of its edge signs is positive. Otherwise, it is 2cos(pi/j), where j stands for the length of the cycle. Several examples are provided. The entire paper relates to some classical results in which the same approach is applied to ordinary graphs. |
|---|---|
| ISSN: | 2307-4116 |