Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graphs; bandwidth; interior boundary; exterior boundary
graphs; bandwidth; interior boundary; exterior boundary
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.
References:
[1] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications. Macmillan, 1976. MR 0411988
[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 10.1002/jgt.3190060302 | MR 0666794
[3] J. Chvátalová and J. Opatrný: The bandwidth problem and operations on graphs. Discrete Math. 61 (1986), 141–150. DOI 10.1016/0012-365X(86)90086-5 | MR 0855320
[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
[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 10.1137/0134037 | MR 0478746
[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
[7] L. H. Harper: Optimal numberings and isoperimetric problems on graphs. J. Combin. Theory 1 (1966), 385–393. DOI 10.1016/S0021-9800(66)80059-5 | MR 0200192 | Zbl 0158.20802
[8] D. J. Kleitman and R. V. Vohra: Computing the bandwidth of interval graphs. SIAM J. Discrete Math. 3 (1990), 373–375. DOI 10.1137/0403033 | MR 1061978
[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 1605101
[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
Search
Partner of
