×

On the problem of bandsize. (English) Zbl 0619.05028

A vertex-numbering of an undirected graph G with N vertices is a bijection f of the vertex set of G onto the number set \(\{\) 1,2,...,N\(\}\). If \(\{\) v,w\(\}\) is an edge of G, then the number \(| f(v)-f(w)|\) is called an edge-differences of f. The bandsize of G, denoted by bs(G), is the minimum number of distinct edge-differences, taken over all vertex-numberings of G. The bandsize is compared with the radius of the graph. For the complete binary tree \(T_ n\) of height n the inequality \(n/7<bs(T_ n)<4n/5+2\) is presented.
Reviewer: B.Zelinka

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akyuz, F.A., Utku, S.: An automatic node-relabelling scheme for bandwidth minimization of stiffness matrices. J. Am. Inst. Aeronautics and Astronautics6, 728–730 (1968)
[2] Chen, K.W., Irani, K.B.: Mapping problem and graph numbering. In: Proc. Workshop on Interconn. Networks for Parallel and Distr. Processing (H.J. Siegel ed.) pp. 41–46. IEEE 1980
[3] Chinn, P.Z., Chvátalová, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices. J. Graph Theory6, 223–254 (1982) · Zbl 0494.05057 · doi:10.1002/jgt.3190060302
[4] Cuthill, E.: Several strategies for reducing the bandwidth of matrices in sparse matrices and their applications (D. Rose and R. Willoughby eds.) pp. 157–166. New York: Plenum Press N.Y. 1972
[5] Dewdney, A.K.: The bandwidth problem for graphs: some recent results. In: 9th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 273–288. Winnipeg: Utilitas Math, 1976 · Zbl 0344.05148
[6] Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity results for bandwidth minimization. SIAM J. Appl. Math.34, 477–495 (1978) · Zbl 0385.05048 · doi:10.1137/0134037
[7] Harper, L.H.: Optimal numberings and isoperimetric problems on graphs. J. Comb. Theory1 385–393 (1966) · Zbl 0158.20802 · doi:10.1016/S0021-9800(66)80059-5
[8] Kahn, J., Kleitman, D.J.: On cross-bandwidth. Discrete Math.33, 385–393 (1981) · Zbl 0451.05039 · doi:10.1016/0012-365X(81)90276-4
[9] Saxe, J.B.: Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algebraic and Discrete Methods1, 363–369 (1980). · Zbl 0496.68032 · doi:10.1137/0601042
[10] Tewarson, R.P.: Row column permutation of sparse matrices. Computer J.10, 300–305 (1967) · Zbl 0155.46902 · doi:10.1093/comjnl/10.3.300
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.