Remarks on Extremal Overfull Graphs

Author(s)
Modjtaba Ghorbani

Affiliation(s)

Department of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Tehran, Iran.

Department of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Tehran, Iran.

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.

M. Ghorbani, "Remarks on Extremal Overfull Graphs,"

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

[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