Optimal linear labelings and eigenvalues of graphs

DOI10.1016/0166-218X(92)90229-4zbMath0759.05087MaRDI QIDQ1192949

Bojan Mohar, Martin Juvan

Publication date: 27 September 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

cutwidth; eigenvalues of graphs; bandwith; min-sum problems; optimal linear labelings

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

Related Items

A survey of graph laplacians, A spectral approach to bandwidth and separator problems in graphs, Laplace eigenvalues of graphs---a survey, A computational study of graph partitioning, Two improved algorithms for envelope and wavefront reduction, On minimum cuts and the linear arrangement problem, A new lower bound for the bipartite crossing number with applications, Lower bounds for the quadratic assignment problem via triangle decompositions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On optimal linear arrangements of trees
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Optimal labelling of a product of two paths
• The NP-completeness of the bandwidth minimization problem
• The bandwidth problem for graphs and matrices—a survey
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Complexity Results for Bandwidth Minimization
• Laplace eigenvalues and bandwidth‐type invariants of graphs