EUVIMEDEUVIMED entdecken
Crossref

Some relations between the largest eigenvalue and the frustration index of a signed graph

Zoran Stanić

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ć.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →