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 条
  • [1] Counting triangles in regular graphs
    He, Jialin
    Hou, Xinmin
    Ma, Jie
    Xie, Tianying
    Journal of Graph Theory, 107 (04): : 759 - 777
  • [2] COUNTING TRIANGLES IN MASSIVE GRAPHS WITH MAPREDUCE
    Kolda, Tamara G.
    Pinar, Ali
    Plantenga, Todd
    Seshadhri, C.
    Task, Christine
    SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2014, 36 (05): : S48 - S77
  • [3] Counting Triangles in Large Graphs on GPU
    Polak, Adam
    2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS (IPDPSW), 2016, : 740 - 746
  • [4] Regular graphs with many triangles are structured
    van der Hoorn, Pim
    Lippner, Gabor
    Mossel, Elchanan
    ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (01):
  • [5] DOULION: Counting Triangles in Massive Graphs with a Coin
    Tsourakakis, Charalampos E.
    Kang, U.
    Miller, Gary L.
    Faloutsos, Christos
    KDD-09: 15TH ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, 2009, : 837 - 845
  • [6] New streaming algorithms for counting triangles in graphs
    Jowhari, H
    Ghodsi, M
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2005, 3595 : 710 - 716
  • [7] Counting Triangles in Large Graphs by Random Sampling
    Wu, Bin
    Yi, Ke
    Li, Zhenguo
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2016, 28 (08) : 2013 - 2026
  • [8] Triangles and subgraph probabilities in random regular graphs
    Gao, Pu
    ELECTRONIC JOURNAL OF COMBINATORICS, 2024, 31 (01):
  • [9] Counting rainbow triangles in edge-colored graphs
    Li, Xueliang
    Ning, Bo
    Shi, Yongtang
    Zhang, Shenggui
    JOURNAL OF GRAPH THEORY, 2024, 107 (04) : 742 - 758
  • [10] Reductions in streaming algorithms, with an application to counting triangles in graphs
    Bar-Yossef, Z
    Kumar, R
    Sivakumar, D
    PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2002, : 623 - 632