论文标题
在横向临界图上定理的光谱加强
Spectral strengthening of a theorem on transversal critical graphs
论文作者
论文摘要
图$ g $的横向组是一组向所有边缘的顶点事件。 $ g $的横向数，用$τ（g）$表示，是$ g $的横向组的最低基数。如果$τ（g-e）<τ（g）$对于e（g）$中的每个边缘$ e \，则无隔离顶点的简单图$ g $被称为$τ$ - 至关重要。对于任何$τ$ - 关键图$ g $，带有$τ（g）= t $，已证明$ | v（g）| \ le 2t $ byerdős和gallai，以及$ | e（g）| \ le {t+1 \ select 2} $ reerdős，hajnal and hajnal and Moon和Moon。最近，Gyárfás和Lehel将其扩展到$ | v（g）| + | e（g）| \ le {t+ 2 \选择2} $。在本文中，我们通过频谱证明了更强的结果。令$ g $为$τ$ - 批评$τ（g）= t $和$ | v（g）| = n $，让$λ_1$表示$ g $的邻接矩阵的最大特征值。我们表明，当$ n+λ_1\ le 2t+1 $具有等值时，并且仅当$ g $是$ tk_2 $，$ k_ {s+1} \ cup（t-s）k_2 $，或$ c_ {2s-1} \ cup（t s）特别是，当$λ_1（g）\ le t $具有平等时，仅当$ g $为$ k_ {t+1} $时。然后，我们将其应用于表明，对于任何非负整数$ r $，我们都有$ n \ left（r+\ frac {λ_1} {2} {2} {2} \ right）\ le {t+r+1 \ select 2} $并表征所有极端图。这意味着$ r | v（g）| + | e（g）| \ le {t+r+1 \选择2} $，它比erdős-hajnal-moon定理和gyárfás-lehel定理强。我们还有其他一些概括。
A transversal set of a graph $G$ is a set of vertices incident to all edges of $G$. The transversal number of $G$, denoted by $τ(G)$, is the minimum cardinality of a transversal set of $G$. A simple graph $G$ with no isolated vertex is called $τ$-critical if $τ(G-e) < τ(G)$ for every edge $e\in E(G)$. For any $τ$-critical graph $G$ with $τ(G)=t$, it has been shown that $|V(G)|\le 2t$ by Erdős and Gallai and that $|E(G)|\le {t+1\choose 2}$ by Erdős, Hajnal and Moon. Most recently, it was extended by Gyárfás and Lehel to $|V(G)| + |E(G)|\le {t+2\choose 2}$. In this paper, we prove stronger results via spectrum. Let $G$ be a $τ$-critical graph with $τ(G)=t$ and $|V(G)|=n$, and let $λ_1$ denote the largest eigenvalue of the adjacency matrix of $G$. We show that $n + λ_1\le 2t+1$ with equality if and only if $G$ is $tK_2$, $K_{s+1}\cup (t-s)K_2$, or $C_{2s-1}\cup (t-s)K_2$, where $2\leq s\leq t$; and in particular, $λ_1(G)\le t$ with equality if and only if $G$ is $K_{t+1}$. We then apply it to show that for any nonnegative integer $r$, we have $n\left(r+ \frac{λ_1}{2}\right) \le {t+r+1\choose 2}$ and characterize all extremal graphs. This implies a pure combinatorial result that $r|V(G)| + |E(G)| \le {t+r+1\choose 2}$, which is stronger than Erdős-Hajnal-Moon Theorem and Gyárfás-Lehel Theorem. We also have some other generalizations.
