Maximum Induced Subgraph of an Augmented Cube

Authors: Meng-Jou Chien, Jheng-Cheng Chen, Chang-Hsiung Tsai

Abstract:

Let max_ζG(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. The n-dimensional augmented cube, denoted as AQn, a variation of the hypercube, possesses some properties superior to those of the hypercube. We study the cases when G is the augmented cube AQn.

Keywords: Interconnection network, Augmented cube, Induced subgraph, Bisection width.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1092818

References:

[1] M. Chen, "The distinguishing number of the augmented cube and hypercube powers,” Discrete Mathematics, 308(11):2330-2336, 2008.
[2] N. W. Chang, S. Y. Hsiueh, "Conditional diagnosability of augmented cubes under the PMC model,”IEEE Transactions on Dependable and Secure Computing, 9(1):46-60, 2012.
[3] S. A. Choudum, V. Sunitha, Khaled A.S., "Augmented cubes,” Networks, 40(2):71-84, 2002.
[4] T. Y. Feng, "A survey of interconnection networks,”IEEE Computer, 14:12-27, 1981.
[5] S. Y. Hsieh, J. Y. Shiu, "Cycle embedding of augmented cubes,”Applied Mathematics and Computation, 191:314-319, 2007.
[6] H. C. Hsu, L. C. Chiang, J. M. Tan, L. H. Hsu, "Fault hamiltonicity of augmented cubes,”Parallel Computing, 31:131-145, 2005.
[7] H. C. Hsu, P. L. Lai, C. H. Tsai, "Geodesic pancyclicity and balanced pancyclicity of augmented cubes,”Information Processing Letters, 101:227-232, 2007.
[8] F. T. Leighton,Introduction to Parallel Algorithms and Architectures: arrays, trees, hypercubes. San Mateo: Morgan Kaufman, 1992.
[9] M. Ma, G. Liu, J. M. Xu, "The super connectivity of augmented cubes,”Information Processing Letters, 106:59-63, 2008.
[10] K. A. S., Abdel-Ghaffar, "Maximum number of edges joining vertices on a cube,”Information processing letters, 87(2):95-99, 2003.
[11] J. Xu,Topological Structure and Analysis of Interconnection networks, Kluwer Academic Publishers, Dordrecht, 2002.
[12] X. Yang, D. J. Evans, G. M. Megson, "Maximum induced subgraph of a recursive circulant,”Information Processing Letters, :293-298, 2005.