Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T15:34:38.610Z Has data issue: false hasContentIssue false

Size, Order, and Connected Domination

Published online by Cambridge University Press:  20 November 2018

Simon Mukwembi*
Affiliation:
University of KwaZulu-Natal, Durban, South Africa e-mail: mukwembi@ukzn.ac.za
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 2014