Premium
On the separation number of a graph
Author(s) -
Miller Zevi,
Pritikin Dan
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190604
Subject(s) - bijection, injection and surjection , bijection , combinatorics , mathematics , hypercube , bipartite graph , graph , discrete mathematics , asymptotically optimal algorithm , algorithm
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.