Proof of a conjecture on the nullity of a connected graph in terms of order and maximum degree
| Autor: | Bolian Liu, Muhuo Liu, Bo Cheng |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Numerical Analysis
Algebra and Number Theory Conjecture 010102 general mathematics 010103 numerical & computational mathematics 01 natural sciences Complete bipartite graph Upper and lower bounds Combinatorics Discrete Mathematics and Combinatorics Order (group theory) Geometry and Topology 0101 mathematics Connectivity Mathematics |
| Zdroj: | Linear Algebra and its Applications. 587:291-301 |
| ISSN: | 0024-3795 |
| DOI: | 10.1016/j.laa.2019.11.011 |
| Popis: | Let G be a connected graph with n vertices, maximum vertex degree Δ ≥ 2 and nullity η. In Q. Zhou et al. (2018) [22] , it was conjectured that η ≤ ( Δ − 2 ) n + 2 Δ − 1 and the upper bound is attained if and only if G is a cycle C n with n divisible by 4 or a complete bipartite graph K n / 2 , n / 2 . In the present paper, this conjecture is proved. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect