Accessibility navigation

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

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


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.

Item Type:Article
ID Code:15469
Uncontrolled Keywords:interconnection networks, recursive circulant, induced subgraph, bisection width, GRAPHS, PANCYCLICITY

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation