Canadian Mathematical Society www.cms.math.ca
 location:  Publications → journals → CMB
Abstract view

# Size, Order, and Connected Domination

Published:2013-07-19
Printed: Mar 2014
• Simon Mukwembi,
University of KwaZulu-Natal, Durban, South Africa
 Format: LaTeX MathJax PDF

## Abstract

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 Turán , 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.
 Keywords: size, connected domination, local independence number, leaf number
 MSC Classifications: 05C69 - Dominating sets, independent sets, cliques

© Canadian Mathematical Society, 2014 : https://cms.math.ca/