Maximum induced subgraph of a recursive circulantYang, 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 Full text not archived in this repository. It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing. To link to this item DOI: 10.1016/j.ipl.2005.03.004 Abstract/SummaryThe 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.
Altmetric Deposit Details University Staff: Request a correction | Centaur Editors: Update this record |
Lists
Lists
