Minimal regular graphs with every edge in a triangle

被引:0
|
作者
Preen, James [1 ]
机构
[1] Cape Breton Univ, Sydney, NS, Canada
来源
AUSTRALASIAN JOURNAL OF COMBINATORICS | 2024年 / 89卷
关键词
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Considering regular graphs with every edge in a triangle we prove lower bounds for the number of triangles in such graphs. For r-regular graphs with r <= 5 we exhibit families of graphs with exactly that number of triangles and then classify all such graphs using line graphs and evencycle decompositions. Examples of ways to create such r-regular graphs with r >= 6 are also given. In the 5-regular case, these minimal graphs are proven to be the only regular graphs with every edge in a triangle that cannot have an edge removed and still have every edge in a triangle.
引用
收藏
页码:385 / 396
页数:12
相关论文
共 50 条
  • [1] CONNECTED GRAPHS WITH EVERY EDGE IN A TRIANGLE
    CALLAN, D
    AMERICAN MATHEMATICAL MONTHLY, 1990, 97 (09): : 848 - 849
  • [2] Quartic Graphs with Every Edge in a Triangle
    Pfender, Florian
    Royle, Gordon F.
    JOURNAL OF GRAPH THEORY, 2016, 82 (02) : 154 - 164
  • [3] Strongly edge triangle regular graphs and a conjecture of Kotzig
    Nair, BR
    Vijayakumar, A
    DISCRETE MATHEMATICS, 1996, 158 (1-3) : 201 - 209
  • [4] A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
    Friedgut, E
    Rödl, V
    Rucinski, A
    Tetali, P
    MEMOIRS OF THE AMERICAN MATHEMATICAL SOCIETY, 2006, 179 (845) : III - +
  • [5] A Triangle Process on Regular Graphs
    Cooper, Colin
    Dyer, Martin
    Greenhill, Catherine
    COMBINATORIAL ALGORITHMS, IWOCA 2021, 2021, 12757 : 310 - 323
  • [6] GENERATION OF MINIMAL TRIANGLE GRAPHS
    BOWEN, R
    MATHEMATICS OF COMPUTATION, 1967, 21 (98) : 248 - +
  • [7] TRIANGLE-FREE REGULAR GRAPHS
    SIDORENKO, AF
    DISCRETE MATHEMATICS, 1991, 91 (02) : 215 - 217
  • [8] On regular triangle-distinct graphs
    Stevanovic, Dragan
    Ghebleh, Mohammad
    Caporossi, Gilles
    Vijayakumar, Ambat
    Stevanovic, Sanja
    COMPUTATIONAL & APPLIED MATHEMATICS, 2024, 43 (06):
  • [9] Edge-regular graphs with regular cliques
    Greaves, Gary R. W.
    Koolen, Jack H.
    EUROPEAN JOURNAL OF COMBINATORICS, 2018, 71 : 194 - 201
  • [10] MINIMAL REGULAR EXTENSIONS OF ORIENTED GRAPHS
    BEINEKE, LW
    PIPPERT, RE
    AMERICAN MATHEMATICAL MONTHLY, 1969, 76 (02): : 145 - &