Counting triangles in regular graphs

被引:0
作者
He, Jialin [1 ]
Hou, Xinmin [2 ,3 ]
Ma, Jie [3 ,4 ]
Xie, Tianying [4 ]
机构
[1] Hong Kong Univ Sci & Technol, Dept Math, Kowloon, Clear Water Bay, Hong Kong 999077, Peoples R China
[2] Univ Sci & Technol China, CAS Wu Wen Tsun Key Lab Math, Hefei, Anhui, Peoples R China
[3] Univ Sci & Technol China, Hefei Natl Lab, Hefei, Peoples R China
[4] Univ Sci & Technol China, Sch Math Sci, Hefei, Anhui, Peoples R China
基金
中国国家自然科学基金;
关键词
extremal graph theory; regular graphs; triangles; CLIQUES;
D O I
10.1002/jgt.23156
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper, we investigate the minimum number of triangles, denoted by t(n, k), in n-vertex k-regular graphs, where n is an odd integer and k is an even integer. The well-known Andrasfai-Erdos-Sos Theorem has established that t (n, k) > 0 if k > 2n/5. In a striking work, Lo has provided the exact value of t (n, k) for sufficiently large n, given that 2n/5 + 12 root n/5 < k < n/2. Here, we bridge the gap between the aforementioned results by determining the precise value of t (n, k) in the entire range 2n/5 < k < n/2. This confirms a conjecture of Cambie, de Joannis de Verclos, and Kang for sufficiently large n.
引用
收藏
页码:759 / 777
页数:19
相关论文
共 50 条
[21]   Counting triangles in real-world networks using projections [J].
Tsourakakis, Charalampos E. .
KNOWLEDGE AND INFORMATION SYSTEMS, 2011, 26 (03) :501-520
[22]   On Vertex-Disjoint Triangles in Tripartite Graphs and Multigraphs [J].
Zou, Qingsong ;
Li, Jiawang ;
Ji, Zizheng .
GRAPHS AND COMBINATORICS, 2020, 36 (05) :1355-1361
[23]   Many triangles in C5-free graphs [J].
Lv, Zequn ;
He, Zhen ;
Lu, Mei .
ADVANCES IN APPLIED MATHEMATICS, 2024, 159
[24]   On Vertex-Disjoint Triangles in Tripartite Graphs and Multigraphs [J].
Qingsong Zou ;
Jiawang Li ;
Zizheng Ji .
Graphs and Combinatorics, 2020, 36 :1355-1361
[25]   Prime graphs of finite groups with a small number of triangles [J].
Tong-Viet, Hung P. .
MONATSHEFTE FUR MATHEMATIK, 2014, 175 (03) :457-484
[26]   Using shortcut edges to maximize the number of triangles in graphs [J].
Dehghani, Sina ;
Fazli, Mohammad Amin ;
Habibi, Jafar ;
Yazdanbod, Sadra .
OPERATIONS RESEARCH LETTERS, 2015, 43 (06) :586-591
[27]   Prime graphs of finite groups with a small number of triangles [J].
Hung P. Tong-Viet .
Monatshefte für Mathematik, 2014, 175 :457-484
[28]   Maximum matchings in regular graphs [J].
Ye, Dong .
DISCRETE MATHEMATICS, 2018, 341 (05) :1195-1198
[29]   Gromov Hyperbolicity of Regular Graphs [J].
Carlos Hernandez-Gomez, J. ;
Rodriguez, Jose M. ;
Sigarreta, Jose M. ;
Torres-Nunez, Yadira ;
Villeta, Maria .
ARS COMBINATORIA, 2017, 130 :395-416
[30]   On independent domination of regular graphs [J].
Cho, Eun-Kyung ;
Choi, Ilkyoo ;
Park, Boram .
JOURNAL OF GRAPH THEORY, 2023, 103 (01) :159-170