Back
 AM  Vol.4 No.8 , August 2013
Remarks on Extremal Overfull Graphs
Abstract: 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.
References

[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

 
 
Top