Share This Article:

Remarks on Extremal Overfull Graphs

Abstract Full-Text HTML XML Download Download as PDF (Size:64KB) PP. 1106-1108
DOI: 10.4236/am.2013.48149    2,481 Downloads   3,688 Views  


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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

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


[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

comments powered by Disqus

Copyright © 2020 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.