Maximum induced subgraph of a recursive circulant

The recursive circulant RC(2n,4) enjoys several attractive topological properties. Let max_ɛG(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that max_ɛRC(2n,4)(m)=∑i=0r(pi/2+i)2pi, where p0>p1>⋯>pr are nonnegative integers defined by m=∑i=0r2pi. We then apply this formula to find the bisection width of RC(2n,4). The conclusion shows that, as n-dimensional cube, RC(2n,4) enjoys a linear bisection width.