Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (3): 667-672.doi: 10.1007/s40305-022-00404-w

Previous Articles     Next Articles

Degree Conditions on Copies of Forests in Graphs

Xiao-Dong Chen1, Shuai-Jun Chen2, Ming-Chu Li3   

  1. 1. School of Mathematics, Liaoning Normal University, Dalian, 116029, Liaoning, China;
    2. College of Science, Liaoning University of Technology, Jinzhou, 121001, Liaoning, China;
    3. School of Softsware, Dalian University of Technology, Dalian, 116024, Liaoning, China
  • Received:2021-06-25 Revised:2022-02-15 Online:2023-09-30 Published:2023-09-07
  • Contact: Xiao-Dong Chen, Shuai-Jun Chen, Ming-Chu Li E-mail:xiaodongchen74@126.com;csj2019@163.com;mingchul@dlut.edu.cn
  • Supported by:
    This research was supported by the National Natural Science Foundation of China (No. 11901268), and Research Fund of the Doctoral Program of Liaoning Normal University (No. 2021BSL011).

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

Key words: Fan-type conditions, Forest, Copy, Small vertex

CLC Number: