Maximum subgraph problem of hiked hypercube and its linear arrangement

Aishwarya, G.; Rajan, R. Sundara; Rajalaxmi, T. M.; Emilet, D. Ahima

doi:10.47974/JDMSC-2389

Open Access Research Article

Maximum subgraph problem of hiked hypercube and its linear arrangement

G. Aishwaryaaishusush0518@gmail.comDepartment of Mathematics Hindustan Institute of Technology and ScienceChennai, Tamil Nadu, 603103, India0009-0004-7879-4346View full profile → , ^*R. Sundara RajanCorresponding authorvprsundar@gmail.comDepartment of Mathematics Rajalakshmi Engineering CollegeChennai, Tamil Nadu, 602105, India0000-0002-1851-6334View full profile → , T. M. Rajalaxmilaxmi.raji18@gmail.comDepartment of Mathematics Sri Sivasubramaniya Nadar College of EngineeringChennai, Tamil Nadu, 603110, India0000-0001-9700-8110View full profile → , D. Ahima Emiletahi.180492@gmail.comDepartment of Mathematics Hindustan Institute of Technology and ScienceDepartment of Mathematics Hindustan Institute of Technology & ScienceChennai, Tamil Nadu, 603103, India0000-0002-3424-2126View full profile →

* Corresponding author · click or hover a name for details

pp. 1673–1684Vol. 29Issue 4April 2026DOI: 10.47974/JDMSC-2389 Crossmark XML

Received:: 01 May 2025
Published Online:: 08 Apr 2026
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-2389
Pages:: 1673–1684

Abstract

Among interconnection topologies, the hypercube is both popular and highly attractive, extensively used in parallel computing and network design due to its versatility and scalability. Its desirable properties have inspired the development of several variants, including the folded hypercube, crossed cube, augmented cube, locally twisted cube, enhanced hypercube, twisted cube, extended hypercube, Mobius cube, and Fibonacci cube, each improving specific aspects such as fault tolerance, communication efficiency, and scalability. A generalized hypercube Qn (S), where S ⊆ {1, 2, …, n}, is an extension of the classic hypercube graph. It has a vertex set {0, 1}n, and edges are formed between vertices whose Hamming distance belongs to the set S. This structure allows for flexible modeling of relationships and connectivity, making it a valuable tool in parallel computing, network design, and combinatorial optimization. This paper focuses on the generalized structure of the hiked hypercube when S = {1, 2, …, j} ⊆ {1, 2, …, n}, and addresses the maximum subgraph problem. Additionally, we determine the minimum linear arrangement of this topology using graph embedding techniques, highlighting its potential in optimizing interconnection networks.

Keywords

Maximum subgraph problem Wirelength Linear arrangement Hiked hypercube

Subject Classifications

05C6005C6205C75

References

[1] J. M. Laborde and R. M. Madani, “Generalized hypercubes and (0,2)-graphs,” Discrete Mathematics, vol. 165-166, pp. 447-459 (1997).
[2] T. Dvorak, I. Havel, J. M. Laborde, and P. Liebl, “Generalized hypercubes and graph embedding with dilation,” Rostocker Mathematisches Kolloquium, vol. 13, pp. 101-107 (1988).
[3] Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transactions on Computers, vol. 37, no. 7, pp. 867-872 (1991).
[4] S. A. Choudum and V. Sunitha, “Augmented cubes,” Networks, vol. 40, no. 2, pp. 71-84 (2002).
[5] A. El-Amawy and S. Latifi, “Properties and performance of folded hypercubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 1, pp. 31-42 (1991).
[6] N. F. Tzeng and S. Wei, “Enhanced hypercubes,” IEEE Transactions on Computers, vol. 40, pp. 284-294 (1991).
[7] R. S. Rajan, A. B. Greeni, and P. L. Joshwa, “Maximum subgraph problem and minimum linear arrangement of generalized Sierpinski networks,” Journal of Graph Algorithms and Applications, vol. 27, no. 9, pp. 767-782 (2023).
[8] R. S. Rajan, R. M. Reji, and T. M. Rajalaxmi, “Maximum subgraph problem for 3-regular Knödel graphs and its wirelength,” In Algorithms and Discrete Applied Mathematics, pp. 403-414 (2023).
[9] M. Miller, R. S. Rajan, N. Parthiban, and I. Rajasingh, “Minimum linear arrangement of incomplete hypercubes,” The Computer Journal, vol. 58, no. 2, pp. 331-337 (2015).
[10] P. Manuel, I. Rajasingh, B. Rajan, and H. Mercy, “Exact wirelength of hypercube on a grid,” Discrete Applied Mathematics, vol. 157, no. 7, pp. 1486-1495 (2009).
[11] G. K. Nandini, S. Klavžar, T. M. Rajalaxmi, and R. S. Rajan, “A note on eccentricity based topological indices of honeycomb, oxide and 2-power interconnection networks,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 26, no. 1, pp. 231-253 (2023).
[12] S. Arulanand, R. S. Rajan, S. Prabhu, and S. Stephen, “Certain domination numbers for Cartesian product of graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 27, no. 3, pp. 1045-1058 (2024).
[13] A. Khobragade, R. Mahajan, H. Langi, R. Mundhe, and S. Ghumbre, “Effective negative triplet sampling for knowledge graph embedding,” Journal of Information and Optimization Sciences, vol. 43, no. 8, pp. 2075-2087 (2022).
[14] G. M. Jose, K. N. Geetha, and K. Somasundaram, “Double power domination in graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 28, no. 6, pp. 2261-2278 (2025).

Views: 95Downloads: 12Citations: 0