Abstract
We say that a set S of vertices is traceable in a graph G whenever there is a path in G containing all vertices of S. In this paper we study the problem of traceability of a prescribed set of vertices in a locally claw-free graph (i.e. a graph in which some specified vertices are not centers of an induced claw). In particular we give sufficient degree conditions restricted to the given set S of vertices for the traceability of S.
Similar content being viewed by others
References
Broersma H.J.: Sufficient conditions for hamiltonicity and traceability in K(1,3)-graphs. In: Hamiltonian cycles in graphs and related topics, Ph.D. Thesis, pp. 45–53. University of Twente (1988)
Čada R.: The *-closure for graphs and claw-free graphs. Discret. Math. 308(23), 5585–5596 (2008)
Čada R., Flandrin E., Li H., Ryjáček Z.: Cycles through given vertices and closures. Discret. Math. 276, 65–80 (2004)
Dirac GA.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. 2, 69–81 (1952)
Fronček D., Ryjáček Z., Skupień Z.: On traceability and 2-factors in claw-free graphs. Discuss. Math. Graph Theory 24, 55–71 (2004)
Frydrych W., Skupień Z.: Non-traceability of large connected claw-free graphs. J. Graph Theory 27(2), 75–86 (1998)
Kovářík O., Mulač M., Ryjáček Z.: A note on degree conditions for hamiltonicity in 2-connected claw-free graphs. Discret. Math. 244(1–3), 253–268 (2002)
Ryjáček Z.: On a closure concept for claw-free graphs. JCTB 70(2), 217–224 (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of the first author was partially supported by grant No. 1M0021620808 of the Czech Ministry of Education. The work on this paper was partly done during author’s stay at L.R.I., Orsay, France.
Rights and permissions
About this article
Cite this article
Čada, R., Flandrin, E. & Kang, H. A Note on Degree Conditions for Traceability in Locally Claw-Free Graphs. Math.Comput.Sci. 5, 21–25 (2011). https://doi.org/10.1007/s11786-011-0074-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11786-011-0074-5