On the separation number of a graph
Zevi Miller, Dan Pritikin · Networks · 1989
Abstract We consider the following graph labeling problem, introduced by Leung et al. (J. Y‐T. Leung, O. Vornberger, and J. D. Witthoff, On some variants of the bandwidth minimization problem. SIAM J. Comput . 13 (1984) 650–667). Let G be a graph of order n , and f a bijection from V(G) to the integers 1 through n. Let |f|, and define s ( G ), the separation number of G , to be the maximum of |f| among all such bijections f . We first derive some basic relations between s ( G ) and other graph parameters. Using a general strategy for analyzing separation number in bipartite graphs, we obtain exact values for certain classes of forests and asymptotically optimal lower bounds for grids and hypercubes.