Geodesic
On Harpers’ result concerning the bandwidths of graphs
Czechoslovak Mathematical Journal, Tome 54 (2004) no. 2, pp. 401-405
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper, we improve the result by Harper on the lower bound of the bandwidth of connected graphs. In addition, we prove that considerating the interior boundary and the exterior boundary when estimating the bandwidth of connected graphs gives the same results.
In this paper, we improve the result by Harper on the lower bound of the bandwidth of connected graphs. In addition, we prove that considerating the interior boundary and the exterior boundary when estimating the bandwidth of connected graphs gives the same results.
Classification : 05C78
Keywords: graphs; bandwidth; interior boundary; exterior boundary 
@article{CMJ_2004_54_2_a11,
     author = {Poon, Kin-Keung},
     title = {On {Harpers{\textquoteright}} result concerning the bandwidths of graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {401--405},
     year = {2004},
     volume = {54},
     number = {2},
     mrnumber = {2059260},
     zbl = {1080.05530},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a11/}
}
TY  - JOUR
AU  - Poon, Kin-Keung
TI  - On Harpers’ result concerning the bandwidths of graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2004
SP  - 401
EP  - 405
VL  - 54
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a11/
LA  - en
ID  - CMJ_2004_54_2_a11
ER  - 
%0 Journal Article
%A Poon, Kin-Keung
%T On Harpers’ result concerning the bandwidths of graphs
%J Czechoslovak Mathematical Journal
%D 2004
%P 401-405
%V 54
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a11/
%G en
%F CMJ_2004_54_2_a11
Poon, Kin-Keung. On Harpers’ result concerning the bandwidths of graphs. Czechoslovak Mathematical Journal, Tome 54 (2004) no. 2, pp. 401-405. http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a11/

[1] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications. Macmillan, 1976. | MR

[2] P. Z. Chinn, J. Chvátalová, A. K. Dewdney and N. E. Gibbs: The bandwidth problem for graphs and matrices—a survey. J.  Graph Theory 6 (1982), 223–254. | DOI | MR

[3] J. Chvátalová and J. Opatrný: The bandwidth problem and operations on graphs. Discrete Math. 61 (1986), 141–150. | DOI | MR

[4] F. R. K. Chung: Labelings of Graphs, Selected Topics in Graph Theory,  III. L.  Beineke, R.  Wilson (eds.), Academic Press, New York, 1988, pp. 151–168. | MR

[5] M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth: Complexity results for bandwidth minimization. SIAM J.  Appl. Math. 34 (1978), 477–495. | DOI | MR

[6] F. Harary: Problem 16. Theory of Graphs and its Applications. Proc. Symp., Smolenice, M. Fiedler (ed.), Czechoslovak Academy of Sciences, Prague, 1964. | MR

[7] L. H. Harper: Optimal numberings and isoperimetric problems on graphs. J.  Combin. Theory 1 (1966), 385–393. | DOI | MR | Zbl

[8] D. J. Kleitman and R. V. Vohra: Computing the bandwidth of interval graphs. SIAM J.  Discrete Math. 3 (1990), 373–375. | DOI | MR

[9] R. R. Korfhage: Numberings of the vertices of graphs. Computer Science Department Technical Report  5, Purdue University, Lafayette, 1966.

[10] Peter C. B. Lam, W. C. Shiu and Y. Lin: Duality in the bandwidth problems. Congressus Numerantium 124 (1997), 117–127. | MR

[11] M. M. Syslo and J. Zak: The bandwidth problem: Critical subgraphs and the solution for caterpillars. Ann. Discrete Math. 16 (1982), 281–286. | MR