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 条
  • [21] On cliques in edge-regular graphs
    Soicher, Leonard H.
    JOURNAL OF ALGEBRA, 2015, 421 : 260 - 267
  • [22] Efficient edge domination in regular graphs
    Cardoso, Domingos M.
    Cerdeira, J. Orestes
    Delorme, Charles
    Silva, Pedro C.
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (15) : 3060 - 3065
  • [23] 3-minimal triangle-free graphs
    Alzohairi, Mohammad
    Boudabbous, Youssef
    DISCRETE MATHEMATICS, 2014, 331 : 3 - 8
  • [24] Almost Regular Edge Colorings and Regular Decompositions of Complete Graphs
    Bryant, Darryn
    Maenhaut, Barbara
    JOURNAL OF COMBINATORIAL DESIGNS, 2008, 16 (06) : 499 - 506
  • [25] Another construction of edge-regular graphs with regular cliques
    Greaves, Gary R. W.
    Koolen, Jack H.
    DISCRETE MATHEMATICS, 2019, 342 (10) : 2818 - 2820
  • [26] Edge-distance-regular graphs are distance-regular
    Camara, M.
    Dalfo, C.
    Delorme, C.
    Fiol, M. A.
    Suzuki, H.
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2013, 120 (05) : 1057 - 1067
  • [27] STRUCTURE OF EDGE-MINIMAL GRAPHS
    KRIEGER, MM
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1969, 16 (01): : 154 - &
  • [28] Typical large graphs with given edge and triangle densities
    Joe Neeman
    Charles Radin
    Lorenzo Sadun
    Probability Theory and Related Fields, 2023, 186 : 1167 - 1223
  • [29] Reconstruction and edge reconstruction of triangle-free graphs
    Clifton, Alexander
    Liu, Xiaonan
    Mahmoud, Reem
    Shantanam, Abhinav
    DISCRETE MATHEMATICS, 2024, 347 (02)
  • [30] MINIMAL REGULAR GRAPHS OF GIRTHS 8 AND 12
    BENSON, CT
    CANADIAN JOURNAL OF MATHEMATICS, 1966, 18 (05): : 1091 - &
12345