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.
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.
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
|