Mathematics

The decycling number of join graphs

  • Hongbo YE ,
  • Chao YANG ,
  • Fuxiang CUI
Expand
  • 1. School of Mathematics, Physics and Statistics, Shanghai University of Engineering Science, Shanghai 201620, China
    2. Center of Intelligent Computing and Applied Statistics, Shanghai University of Engineering Science, Shanghai 201620, China

Received date: 2020-11-18

  Online published: 2022-01-18

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}$ .

Cite this article

Hongbo YE , Chao YANG , Fuxiang CUI . The decycling number of join graphs[J]. Journal of East China Normal University(Natural Science), 2022 , 2022(1) : 17 -21 . DOI: 10.3969/j.issn.1000-5641.2022.01.003

References

1 魏二玲, 李益凡. 广义 Petersen 图的消圈数与上可嵌入性. 数学学报(中文版), 2013, 56 (2): 211- 216.
2 KARP R. Reducibility Among Combinatorial Problems, Complexity of Computer Computations [M]. New York: Plenum Press, 1972.
3 FESTA P, PARDALOS P M, RESENDE M G C. Feedback Set Problem [M]. Kluwer: Kluwer Academic Publishers, 2018.
4 GRUNBAUM B. Acyclic colorings of planar graphs. Israel Journal of Mathematics, 1973, 14, 390- 408.
5 BONDY J A, MURTY U S R. Graph Theory and Related Topics [M]. New York: Academic Press, 1979.
6 BORODIN O V. On acyclic colorings of planar graphs. Discrete Mathematics, 1979, 25, 211- 236.
7 SKREKOVSKI R. On the critical point-arboricity graphs. Journal of Graph Theory, 2002, 39, 50- 61.
8 BAU S, BEINEKE L W. The decycling number of graphs. Australasian Journal of Combinatorics, 2002, 25, 285- 298.
Outlines

/