Forbidden Restrictions and the Existence of P≥2-Factor and P≥3-Factor

Abstract

The existence of factor and fractional factor in network graph in various settings has raised much attention from both mathematicians and computer scientists. It implies the availability of data transmission and network segmentation in certain special settings. In our paper, we consider P≥2-factor and P≥3-factor which are two special cases of general H-factor. Specifically, we study the existence of these two kinds of path factor when some subgraphs are forbidden, and several conclusions on the factor-deleted graph, factor critical-covered graph, and factor uniform graph are given with regards to network parameters. Furthermore, we show that these bounds are best in some sense.