A subset of S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it is both acyclic and dominating. The minimum cardinali...A subset of S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by γα(G), is called the acyclic domination number of G. S. M. Hedetniemi et al. on 2000 introduced the concept of acyclic domination and posed the following open problem: Is γα(G) ≤ δ(G) for any graph whose diameter is two? In this paper, we give a counterexample which disproves the problem.展开更多
基金This research is supported by the National Natural Science Foundation of ChinaThis project is supported by Nanjing University Talent Development Foundation.
文摘A subset of S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by γα(G), is called the acyclic domination number of G. S. M. Hedetniemi et al. on 2000 introduced the concept of acyclic domination and posed the following open problem: Is γα(G) ≤ δ(G) for any graph whose diameter is two? In this paper, we give a counterexample which disproves the problem.
