关键词: 图, 消圈数, 联图

Abstract:

Let $G = (V, E)$ be a simple graph. For any vertex set $S$ of V, if $G - S$ is acyclic, then $S$ is a decycling set of G; the minimum size of a decyling set is called the decycling number of G, denoted by $\phi \left( G \right)$ . In this paper, we consider the decycling problem of join graphs and obtain the exact value for the decycling number of some types of join graphs. Let ${G_m}$ and ${G_n}$ be simple connected graphs of the order m and n, respectively. Then the decycling number of the join graph ${G_m} \vee {G_n}$ satisfies: $\min \{ m,n\} \leqslant \phi ({G_m} \vee {G_n}) \leqslant$ $\min \{ m + \phi ({G_n}),n + \phi ({G_m})\}$ . The results presented in this paper confirm that the upper bound for the above inequality is tight. In particular, if ${G_m}$ and ${G_n}$ are trees, then we can obtain the exact value for the decycling number of ${G_m} \vee {G_n}$ .

Key words: graph, decycling number, join graphs