On construction for trees making the equality hold in Vizing's conjecture
Weisheng Zhao, Ruizhi Lin, Junqing Cai · Journal of Graph Theory · 2022
Abstract In 1968, Vizing gave a conjecture: for any graphs and , which is now still open. In the text book “Domination in Graph: Advanced Topices” edited by Haynes et al., they listed such a question: is there a structural characterization of the graphs such that there exists a graph with ? In this paper, we restrict to be a tree and prove that: for any tree , there exists a nonempty graph such that if and only if . Based on this, we obtain a construction of the tree class is a nontrivial tree and there exists a nonempty graph such that .