Decycling d-ary n-dimensional cubes

Abstract

The decycling number of a graph G is the minimnm number of vertices whose removal from G results in an acyclic subgraph. The d-ary n-dimensional cubes are n-fold cartesian product graphs of complete graph on d vertices. When d = 2, it reduces to the ordinary n-dimensional hypercubes. In this paper, we show that the decycling number f(d, n) of the d-ary n-dimensional cubes Qn(d) can be bounded as follows: (d-1)V-2 < f(d,n) <(d-1-<r-where M = (d-l)(2nd-3d + 2) + 1. © 2020 Utilitas Mathematica Publishing Inc.. All rights reserved.