On Tight (k,ℓ)‐Stable Graphs

ABSTRACT For integers , a graph is ‐stable if for every with . A recent result of Dong and Wu states that every ‐stable graph satisfies . A ‐stable graph is tight if ; and ‐tight for some integer if . In this paper, we first prove that for all , the only tight ‐stable graphs are and , answering a question of Dong and Luo. We then prove that for all nonnegative integers with , every ‐tight ‐stable graph has at most vertices, answering a question of Dong and Luo in the negative.