Maximum induced subgraph of a recursive circulant

Yang, X. F., Evans, D. J. and Megson, G. M. (2005) Maximum induced subgraph of a recursive circulant. Information Processing Letters, 95 (1). pp. 293-298. ISSN 0020-0190 doi: 10.1016/j.ipl.2005.03.004

Abstract/Summary

The recursive circulant RC(2(n), 4) enjoys several attractive topological properties. Let max_epsilon(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_epsilon(RC(2n,4))(m) = Sigma(i)(r)=(0)(p(i)/2 + i)2(Pi), where p(0) > p(1) > ... > p(r) are nonnegative integers defined by m = Sigma(i)(r)=(0)2(Pi). We then apply this formula to find the bisection width of RC(2(n), 4). The conclusion shows that, as n-dimensional cube, RC(2(n), 4) enjoys a linear bisection width. (c) 2005 Elsevier B.V. All rights reserved.