2022/04/21 by Sizhong Zhou, Zhou, Sizhong, Zhiren Sun +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2204.09842
For a set H of connected graphs, a spanning subgraph H of G is called an H-factor of G if each component of H is isomorphic to an element of H. A graph G is called an H-factor uniform graph if for any two edges e1 and e2 of G, G has an H-factor covering e1 and excluding e2. Let each component in H be a path with at least d vertices, where d≥2 is an integer. Then an H-factor and an H-factor uniform graph are called a P≥ d-factor and a P≥ d-factor uniform graph, respectively. In this article, we verify that (\romannumeral1) a 2-edge-connected graph G is a P≥3-factor uniform graph if δ(G)>(α(G)+4)/(2); (\romannumeral2) a (k+2)-connected graph G of order n with n≥5k+3-(3)/(5γ-1) is a P≥3-factor uniform graph if |NG(A)|>γ(n-3k-2)+k+2 for any independent set A of G with |A|=\lfloorγ(2k+1)\rfloor, where k is a positive integer and γ is a real number with (1)/(3)≤γ≤1.