On critical spanning trees and the linear-arrangement problem

For a simple finite graph G = (V, E) of order n, the optimal linear-arrangement problem seeks a vertex labeling f: V [right arrow] {1, 2, ..., n} for which the expression [[summation of].sub.({u,v})[member of]E]|f(u) - f(v)| is minimized. In this brief, we examine the following notion. Given some F G, is there a spanning tree of G having an optimal labeling that is also optimal for G? We specify some graph classes, which always exhibit these critical spanning trees and demonstrate how to construct them. Index Terms--Critical subgraph, graph theory, linear arrangement.