Triangle-free graphs with large minimum common degree

Jian Wang

doi:10.1016/j.dam.2025.09.030

Triangle-free graphs with large minimum common degree

2025-10-01

0

PRE

AI

DOI：10.1016/j.dam.2025.09.030

原文链接

原文求助

摘要

En 中文

设G是一个图。对于x ∈ V(G)，令N(x) = {y ∈ V(G) : xy ∈ E(G)}。图G的最小共同度，记作δ2(G)，定义为G中所有非边xy的|N(x) ∩ N(y)|的最小值。1982年，H & auml;ggkvist证明了每个最小度大于3n8的无三角形图同态于长度为5的圈。本文证明每个最小共同度大于8n的无三角形图同态于长度为5的圈，这蕴含了H & auml;ggkvist的结果。M & ouml;bius梯图的平衡膨胀表明该结果是最佳可能的。(c) 2025 Elsevier B.V. 版权所有，包括文本和数据挖掘、AI训练以及类似技术的权利。

Keyword:

Triangle-free

Minimum common degree

The blow-up of C5

Triangle-free graphs with large minimum common degree

摘要

期刊

机构

引用论文