Embedding of hypercubes into necklace, windmill and snake graphs

DOI10.1016/j.ipl.2012.03.006zbMath1243.68229OpenAlexW2025669150MaRDI QIDQ436587

Indra Rajasingh, R. Sundara Rajan, Bharathi Rajan

Publication date: 25 July 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.03.006

zbMATH Keywords

embeddinghypercubesinterconnection networkscongestionwirelengthedge isoperimetric problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Mathematical problems of computer architecture (68M07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Results on Total Restrained Domination number and subdivision number for certain graphs ⋮ Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees ⋮ Embedding Wheel - like Networks ⋮ Bothway embedding of circulant network into grid ⋮ A linear time algorithm for embedding hypercube into cylinder and torus ⋮ Maximum incomplete recursive circulants in graph embeddings ⋮ Node set optimization problem for complete Josephus cubes ⋮ Embedding of recursive circulants into certain necklace graphs ⋮ Characterization of the congestion lemma on layout computation ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Embeddings of circulant networks
• Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
• Minimum average congestion of enhanced and augmented hypercubes into complete binary trees
• Embedding of tori and grids into twisted cubes
• Embedding meshes/tori in faulty crossed cubes
• Dense sets and embedding binary trees into hypercubes
• Embedding of meshes in Möbius cubes
• On embeddings of snarks in the torus
• Embedding meshes into locally twisted cubes
• Path embedding in star graphs
• Exact wirelength of hypercubes on a grid
• Embedding the incomplete hypercube in books
• The cyclic cutwidth of trees
• Efficient embeddings of ternary trees into hypercubes.
• An edge-isoperimetric problem for powers of the Petersen graph
• Wirelength of \(1\)-fault Hamiltonian graphs into wheels and fans
• Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
• The congestion of \(n\)-cube layout on a rectangular grid
• Embedding meshes into crossed cubes
• Complete path embeddings in crossed cubes
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• Embedding of cycles and wheels into arbitrary trees
• Efficient embeddings of grids into grids
• Optimal embeddings of generalized ladders into hypercubes
• Embedding complete trees into the hypercube