Bit-Shun Tam

dblp:317/3432 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2026
0000-0002-7525-3155ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2026 Bounds for zero forcing numbers of connected graphs with fixed order and maximum degree
abstract
The zero forcing number Z ( G ) of a graph G was proposed by the AIM Minimum Rank-Special Graphs Work Group as an upper bound on the nullities of matrices associated with G . Recently, the study of upper bounds for the zero forcing number and for the nullity of a connected graph in terms of its order and maximum degree has received much attention. In particular, Gentner and Rautenbach (2018) proved that if G is a connected graph of order n with maximum degree Δ ≥ 3 , then Z ( G ) ≤ Δ − 2 Δ − 1 n except when G is a complete graph, a complete bipartite graph of the form K n 1 , n 2 with | n 1 − n 2 | ≤ 1 , or is equal to W 1 , W 2 , where W 1 and W 2 are two specific graphs of order 5 and 7, respectively. In this paper we identify all connected graphs G of order n with maximum degree Δ ≥ 3 that satisfy Z ( G ) = Δ − 2 Δ − 1 n , and prove that if Z ( G ) < ( Δ − 2 ) n Δ − 1 then Z ( G ) ≤ ( Δ − 2 ) n − 1 Δ − 1 . We find one graph missing from the list of exceptional graphs in the above-mentioned result of Gentner and Rautenbach and provide an independent alternative proof for the amended result. A new proof technique which is based on the concept of maximal augmenting path is introduced in the course of proofs. We also rederive or improve existing upper bounds for the nullity of a connected graph in terms of its order and maximum degree.
Chaohui Chen, Muhuo Liu, Bit-Shun Tam
Discret. Appl. Math.3
2022 Graphs G with nullity 2c(G)+p(G)-1
Sarula Chang, Bit-Shun Tam, Jianxi Li, Yirong Zheng
Discret. Appl. Math.2