| Title:
|
On Harpers’ result concerning the bandwidths of graphs (English) |
| Author:
|
Poon, Kin-Keung |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
54 |
| Issue:
|
2 |
| Year:
|
2004 |
| Pages:
|
401-405 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
graphs |
| Keyword:
|
bandwidth |
| Keyword:
|
interior boundary |
| Keyword:
|
exterior boundary |
| MSC:
|
05C78 |
| idZBL:
|
Zbl 1080.05530 |
| idMR:
|
MR2059260 |
| . |
| Date available:
|
2009-09-24T11:13:42Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127897 |
| . |
| Reference:
|
[1] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications.Macmillan, 1976. MR 0411988 |
| Reference:
|
[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. MR 0666794, 10.1002/jgt.3190060302 |
| Reference:
|
[3] J. Chvátalová and J. Opatrný: The bandwidth problem and operations on graphs.Discrete Math. 61 (1986), 141–150. MR 0855320, 10.1016/0012-365X(86)90086-5 |
| Reference:
|
[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 1205400 |
| Reference:
|
[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. MR 0478746, 10.1137/0134037 |
| Reference:
|
[6] F. Harary: Problem 16.Theory of Graphs and its Applications. Proc. Symp., Smolenice, M. Fiedler (ed.), Czechoslovak Academy of Sciences, Prague, 1964. MR 0175111 |
| Reference:
|
[7] L. H. Harper: Optimal numberings and isoperimetric problems on graphs.J. Combin. Theory 1 (1966), 385–393. Zbl 0158.20802, MR 0200192, 10.1016/S0021-9800(66)80059-5 |
| Reference:
|
[8] D. J. Kleitman and R. V. Vohra: Computing the bandwidth of interval graphs.SIAM J. Discrete Math. 3 (1990), 373–375. MR 1061978, 10.1137/0403033 |
| Reference:
|
[9] R. R. Korfhage: Numberings of the vertices of graphs.Computer Science Department Technical Report 5, Purdue University, Lafayette, 1966. |
| Reference:
|
[10] Peter C. B. Lam, W. C. Shiu and Y. Lin: Duality in the bandwidth problems.Congressus Numerantium 124 (1997), 117–127. MR 1605101 |
| Reference:
|
[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 0686313 |
| . |
