Some relations between the largest eigenvalue and the frustration index of a signed graph
American Journal of Combinatorics · 2022
DOI: 10.63151/amjc.v1i.7 ↗Kurz gefasst
Fachartikel in der Zeitschrift American Journal of Combinatorics, 2022. Verfasst von Zoran Stanić.
Abstract (Originalsprache)
Let \(\dot{G}\) be a signed graph with \(n\) vertices and the frustration index \(\ell\). We prove the existence of \(k~(k\geq \ell)\) edges \(e_1, e_2, \ldots, e_k\) of \(\dot{G}\) such that \[\begin{equation*}\lambda_1(\dot{G})\leq \lambda_1(\dot{G}-e_1)\leq \lambda_1(\dot{G}-e_1-e_2)\leq\cdots\leq\lambda_1\Big(\dot{G}-\sum_{i=1}^k e_i\Big),\end{equation*}\] where \(\lambda_1\) denotes the largest eigenvalue, and an inequality in above chain is strict unless the signed graph on the left hand side is disconnected with at least two components with the same largest eigenvalue. We also prove the existence of a connected balanced spanning subgraph \(\dot{H}\) such that \[\begin{equation*}\ell\geq \frac{\big(\lambda_1(\dot{H}\big)-\lambda_1(\dot{G})\big)\big(\Delta+\lambda_1(\dot{H})\big)}{2\Delta}\sqrt{\frac{n}{n-1}},\end{equation*}\] where \(\Delta\) is the maximum vertex degree in \(\dot{H}\), along with the equality precisely in the trivial case when \(\dot{G}\) is balanced. We also derive some consequences of the previous results.
Zitieren
APA
Stanić, Z. (2022). Some relations between the largest eigenvalue and the frustration index of a signed graph. American Journal of Combinatorics. https://doi.org/10.63151/amjc.v1i.7
Vancouver
Stanić Z. Some relations between the largest eigenvalue and the frustration index of a signed graph. American Journal of Combinatorics. 2022. doi:10.63151/amjc.v1i.7
BibTeX
@article{Stani2022,
author = {Stanić, Zoran},
title = {Some relations between the largest eigenvalue and the frustration index of a signed graph},
journal = {American Journal of Combinatorics},
year = {2022},
doi = {10.63151/amjc.v1i.7}
}
EUVIMED