Binding Number, $k$-Factor and Spectral Radius of Graphs
The Electronic Journal of Combinatorics · 09.02.2024 · 31 (1)
DOI: 10.37236/12165 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 09.02.2024. Verfasst von Dandan Fan und 1 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref).
Abstract (Originalsprache)
The binding number $b(G)$ of a graph $G$ is the minimum value of $|N_{G}(X)|/|X|$ taken over all non-empty subsets $X$ of $V(G)$ such that $N_{G}(X)\neq V(G)$. The association between the binding number and toughness is intricately interconnected, as both metrics function as pivotal indicators for quantifying the vulnerability of a graph. The Brouwer-Gu Theorem asserts that for any $d$-regular connected graph $G$, the toughness $t(G)$ always at least $\frac{d}{\lambda}-1$, where $\lambda$ denotes the second largest absolute eigenvalue of the adjacency matrix. Inspired by the work of Brouwer and Gu, in this paper, we investigate $b(G)$ from spectral perspectives, and provide tight sufficient conditions in terms of the spectral radius of a graph $G$ to guarantee $b(G)\geq r$. The study of the existence of $k$-factors in graphs is a classic problem in graph theory. Katerinis and Woodall state that every graph with order $n\geq 4k-6$ satisfying $b(G)\geq 2$ contains a $k$-factor where $k\geq 2$. This leaves the following question: which $1$-binding graphs have a $k$-factor? In this paper, we also provide the spectral radius conditions of $1$-binding graphs to contain a perfect matching and a $2$-factor, respectively.
Zitieren
APA
Fan, D., & Lin, H. (2024). Binding Number, $k$-Factor and Spectral Radius of Graphs. The Electronic Journal of Combinatorics, 31(1). https://doi.org/10.37236/12165
Vancouver
Fan D, Lin H. Binding Number, $k$-Factor and Spectral Radius of Graphs. The Electronic Journal of Combinatorics. 2024;31(1). doi:10.37236/12165
BibTeX
@article{Fan2024,
author = {Fan, Dandan and Lin, Huiqiu},
title = {Binding Number, $k$-Factor and Spectral Radius of Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2024},
volume = {31},
number = {1},
doi = {10.37236/12165}
}
EUVIMED