图的谱半径和$P_{\ge 2}$-因子的存在性

The Spectral Radius of Graphs and the Existence of $P_{\ge 2}$-Factors

摘要: 设$G$ 是简单连通图，若图$G$ 有一个生成子图$F$ ，该生成子图$F$ 的每个连通分支是阶数至少为2的路，则称图$G$ 含有一个$P_{\ge 2}$ -因子。本文给出了图$G$ 谱半径的一个下界，保证了该类图$P_{\ge 2}$ -因子的存在性，以及刻画了谱半径达到下界时对应的极图结构。设$f$ 为一个函数，对图$G$ 中的每条边赋一个落在区间$\left[0,1\right]$ 上的函数值。若满足${\displaystyle \sum _{e\in \Gamma \left(v\right)}f\left(e\right)}\le 1$ ，其中$\Gamma \left(v\right)$ 是与点$v$ 相邻的边的集合，则称$f$ 是图$G$ 的一个分数匹配。本文还根据分数完美匹配定理给出了图$G$ 含有一个$P_{\ge 2}$ -因子的充分性条件。

Abstract: Let $G$ be a simple connected graph. A $P_{\ge 2}$ -factor of a graph $G$ is a spanning subgraph $F$ of $G$ such that each component of $F$ is a path of order at least $k$ ($k\ge 2$ ). This paper provides a lower bound for the spectral radius of graph G, guarantees the existence of a $P_{\ge 2}$ -factor in such graphs, and characterizes the extremal graph structures when the spectral radius reaches the lower bound. A fractional matching is a function $f$ that assigns to each edge of a graph a number in [0, 1] so that, for each vertex $v$ , we have ${\displaystyle \sum f\left(e\right)}\le 1$ where the sum is taken over all edges incident to $v$ . This paper also provides a sufficient condition for a graph $G$ to contain a $P_{\ge 2}$ -factor based on the perfect matching theorem.