EUVIMEDEUVIMED entdecken
Crossref

Binding Number, $k$-Factor and Spectral Radius of Graphs

Dandan Fan, Huiqiu Lin

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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