Characterizing P≥2-Factor Deleted Graphs with Respect to the Size or the Spectral Radius

摘要

A graph G has a P->= k -factor if G has a spanning subgraph H such that every component of H is a path of order at least k. A graph G is P->= k-factor deleted if G-e has a P->= k-factor for each edge e of G. In this paper, we give two necessary and sufficient conditions defining a P->= 2-factor deleted graph and a P->= 3-factor deleted graph, respectively. Based on the result of P->= 2-factor deleted graphs, we establish respectively a lower bound on the size and a lower bound on the spectral radius to ensure whether or not a graph is P->= 2-factor deleted. Furthermore, by constructing extremal graphs, we show that all the above bounds are best possible.

关键词