For a graph G, let $ \mu (G)=\min \{\max \{{d}(x),{d}(y)\}:x\ne y,xy\notin E(G), x,y\in V(G)\} $ if G is non-complete, otherwise, $ \mu (G)=+\infty. $ For a given positive number s, we call that a graph G satisfies Fan-type conditions if $ \mu (G)\geqslant s. $ Suppose $ \mu (G)\geqslant s, $ then a vertex v is called a small vertex if the degree of v in G is less than s. In this paper, we prove that for a forest F with m edges, if G is a graph of order $ n\geqslant |F| $ and $ \mu (G)\geqslant m $ with at most $ \max \{n-2m,0\} $ small vertices, then G contains a copy of F. We also give examples to illustrate both the bounds in our result are best possible.
Xiao-Dong Chen, Shuai-Jun Chen, Ming-Chu Li
. Degree Conditions on Copies of Forests in Graphs[J]. Journal of the Operations Research Society of China, 2023
, 11(3)
: 667
-672
.
DOI: 10.1007/s40305-022-00404-w
[1] Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Elsevier Science Publishing Co., New York (1976)
[2] Fan, G.H.: New sufficient conditions for cycles in graphs. J. Combin. Theory Ser. B 37(3), 221–227(1984)
[3] Fujita, S.: Degree conditions for the partition of a graph into cycles, edges and isolated vertices. Discrete Math. 309, 3534–3540(2009)
[4] Yan, J., Zhang, S.H., Cai, J.Q.: Fan-type condition on disjoint cycles in a graph. Discrete Math. 341, 1160–1165(2018)
[5] Erdős, P.: Extremal problems in graph theory. In: Fiedler, M. (ed.) Theory of Graphs and its Applications, pp. 29–36. Academic Press, New York (1964)
[6] Brandt, S.: Subtrees and subforests of graphs. J. Combin. Theory Ser. B 61, 63–70(1994)
[7] Babu, C.S., Diwan, A.A.: Degree conditions for forests in graphs. Discrete Math. 301, 228–231(2005)
[8] Ajtai, M., Komlós, J., Szemerédi, E.: On a conjecture of Loebl, graph theory, combinatorics, and applications, In: Y. Alavi, A. Schwenk (Eds.), Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs on the occasion of Paul Erdös's 80th birthday, Kalamazoo, MI, pp. 1135–1146(1992)
