Remarks on Extremal Overfull Graphs


An overfull graph is a graph whose number of its edges is greater than the product of its maximum degree and [n/2] , where n is the number of vertices. In this paper, some extremals of overfull graphs are presented. We also classify all plannar overfull graphs.

Share and Cite:

M. Ghorbani, "Remarks on Extremal Overfull Graphs," Applied Mathematics, Vol. 4 No. 8, 2013, pp. 1106-1108. doi: 10.4236/am.2013.48149.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] G. Chartrand and F. Zhang, “Chromatic Graph Theory,” Chapman and Hall/CRC, London, 2008. doi:10.1201/9781584888017
[2] A. G. Chetwynd and A. J. W. Hilton, “Star Multigraphs with Three Vertices of Maximum Degree,” Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 100, No. 2, 1986, pp. 303-317. doi:10.1017/S030500410006610X
[3] T. Niessen, “How to Find Overfull Subgraphs in Graphs with Large Maximum Degree,” Discrete Applied Mathe matics, Vol. 51, No. 1-2, 1994, pp. 117-125.
[4] M. Plantholt, “Overfull Conjecture for Graphs with High Minimum Degree,” Journal of Graph Theory, Vol. 47, No. 2, 2004, pp. 73-80. doi:10.1002/jgt.20013

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.