Size, Order, and Connected Domination

作者：Mukwembi Simon^*

来源：Canadian Mathematical Bulletin, 2014, 57(1): 141-144.

DOI：10.4153/CMB-2013-020-5

• size
• connected domination
• local independence number
• leaf number

We give a sharp upper bound on the size of a triangle-free graph of a given order and connected domination. Our bound, apart from strengthening an old classical theorem of Mantel and of Turan improves on a theorem of Sanchis. Further, as corollaries, we settle a long standing conjecture of Graffiti on the leaf number and local independence for triangle-free graphs and answer a question of Griggs, Kleitman, and Shastri on a lower bound of the leaf number in triangle-free graphs.

• 出版日期2014-3