AM  Vol.4 No.8 , August 2013
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.

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