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 条
  • [31] Tree-minimal graphs are almost regular
    Dellamonica, D., Jr.
    Haxell, P.
    Luczak, T.
    Mubayi, D.
    Nagle, B.
    Person, Y.
    Rodl, V.
    Schacht, M.
    JOURNAL OF COMBINATORICS, 2012, 3 (01) : 49 - 62
  • [32] Minimal Contagious Sets in Random Regular Graphs
    Guggiola, Alberto
    Semerjian, Guilhem
    JOURNAL OF STATISTICAL PHYSICS, 2015, 158 (02) : 300 - 358
  • [33] Minimal regular 2-graphs and applications
    Hongbing Fan
    Guizhen Liu
    Jiping Liu
    Science in China Series A, 2006, 49 : 158 - 172
  • [34] Some spectral inequalities for triangle-free regular graphs
    Koledin, Tamara
    Stanic, Zoran
    FILOMAT, 2013, 27 (08) : 1561 - 1567
  • [35] Minimal regular 2-graphs and applications
    Fan, HB
    Liu, GZ
    Liu, JP
    SCIENCE IN CHINA SERIES A-MATHEMATICS, 2006, 49 (02): : 158 - 172
  • [36] Minimal Contagious Sets in Random Regular Graphs
    Alberto Guggiola
    Guilhem Semerjian
    Journal of Statistical Physics, 2015, 158 : 300 - 358
  • [37] Minimal regular 2-graphs and applications
    FAN Hongbing
    School of Mathematics and System Science
    Department of Mathematics and Computer Science
    Science in China(Series A:Mathematics), 2006, (02) : 158 - 172
  • [38] A NOTE ON BIPARTITE SUBGRAPHS OF TRIANGLE-FREE REGULAR GRAPHS
    LOCKE, SC
    JOURNAL OF GRAPH THEORY, 1990, 14 (02) : 181 - 185
  • [39] Typical large graphs with given edge and triangle densities
    Neeman, Joe
    Radin, Charles
    Sadun, Lorenzo
    PROBABILITY THEORY AND RELATED FIELDS, 2023, 186 (3-4) : 1167 - 1223
  • [40] Smallest regular and almost regular triangle-free graphs without perfect matchings
    Volkmann, Lutz
    ARS COMBINATORIA, 2013, 111 : 463 - 472
12345