Article ID Journal Published Year Pages File Type
10331335 Information Processing Letters 2005 6 Pages PDF
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Maximum induced subgraph of a recursive circulant
Authors
, , ,