CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Publications        
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 size, connected domination, local independence number, leaf number
MSC Classifications: 05C69 show english descriptions Dominating sets, independent sets, cliques 05C69 - Dominating sets, independent sets, cliques
 

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