A note on the characterization of claw-free and paw-free graphs

Author(s): Phillip Mafuta1,2, Josiah Mushanyu3,2
1Department of Mathematics and Applied Mathematics IB74, University of the Free State, Bloemfontein, South Africa
2Department of Mathematics and Computational Sciences, University of Zimbabwe, Harare, Zimbabwe
3Department of Computing, Mathematical and Statistical Sciences, University of Namibia, Windhoek, Namibia
Copyright © Phillip Mafuta, Josiah Mushanyu. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

A number of results on claw-free, paw-free graphs have been presented in the literature. Although the proofs of such results are elegant, sound and valid, it has gone unnoticed that all the results about claw-free, paw-free graphs in the literature are a consequence of a result by Olariu [1]. The note, apart from covering the aforementioned gap, also provides an alternate proof to a result by Faudree and Gould found in [2] in that, an unnoticed consequence resulted in the characterization of claw-free, paw-free graphs.

Keywords: Forbidden Sub-graphs; Pancyclicity; Hamiltonicity; Traceability.