A note on minimum linear arrangement for BC graphs

DOI10.1142/S1793830918500234MaRDI QIDQ4634526zbMATH OpenFDO

Authors Xiaofang Jiang, Qinghui Liu, N. Parthiban, R. Sundara Rajan

Publication date 10 April 2018

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.01149

zbMATH Keywords

BC graphsminimum linear arrangement

Mathematics Subject Classification ID

Connectivity (05C40) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: A linear arrangement is a labeling or a numbering or a linear ordering of the vertices of a graph. In this paper we solve the minimum linear arrangement problem for bijective connection graphs (for short BC graphs) which include hypercubes, M"{o}bius cubes, crossed cubes, twisted cubes, locally twisted cube, spined cube, $Z$-cubes, etc. as the subfamilies.

Recommendations

• Lower bounds for the minimum linear arrangement of a graph
• A New Lower Bound for the Minimum Linear Arrangement of a Graph
• Minimum Linear Arrangement of Generalized Sierpinski Graphs
• scientific article; zbMATH DE number 6387522
• A note about some properties of BC graphs
• Minimum linear arrangement of chord graphs
• Minimum Linear Arrangement of Series-Parallel Graphs
• Decorous lower bounds for minimum linear arrangement
• Minimal cutwidth linear arrangements of abelian Cayley graphs
• The linear arrangement problem on recursively constructed graphs

Cites work

• A note about some properties of BC graphs
• An optimal time algorithm for minimum linear arrangement of chord graphs
• Embeddings of circulant networks
• scientific article; zbMATH DE number 1303526 (Why is no real title available?)
• scientific article; zbMATH DE number 6131601 (Why is no real title available?)
• Linear layout of locally twisted cubes
• Linear wirelength of folded hypercubes
• On the t/k-diagnosability of BC networks
• Optimal Assignments of Numbers to Vertices
• Optimal Linear Arrangement of Interval Graphs
• The locally twisted cubes
• The Mobius cubes
• The spined cube: a new hypercube variant with smaller diameter

Cited in

(6)

• Embedding algorithm of spined cube into grid structure and its wirelength computation
• Minimum linear arrangement of the Cartesian product of optimal order graph and path
• Linear and cyclic node arrangement of Cartesian product of certain graphs
• Maximum subgraph problem for 3-regular Knödel graphs and its wirelength
• Maximum subgraph and wirelength analysis of extended Sierpiński networks in parallel computing
• An upper bound for edge congestion and the exact wirelength of embedding onto BC graphs

This page was built for publication: A note on minimum linear arrangement for BC graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634526)