Geodesic
Size, Order, and Connected Domination
Canadian mathematical bulletin, Tome 57 (2014) no. 1, pp. 141-144

Voir la notice de l'article provenant de la source Cambridge University Press

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.
DOI : 10.4153/CMB-2013-020-5
Mots-clés : 05C69, size, connected domination, local independence number, leaf number 
Mukwembi, Simon. Size, Order, and Connected Domination. Canadian mathematical bulletin, Tome 57 (2014) no. 1, pp. 141-144. doi: 10.4153/CMB-2013-020-5
@article{10_4153_CMB_2013_020_5,
     author = {Mukwembi, Simon},
     title = {Size, {Order,} and {Connected} {Domination}},
     journal = {Canadian mathematical bulletin},
     pages = {141--144},
     year = {2014},
     volume = {57},
     number = {1},
     doi = {10.4153/CMB-2013-020-5},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-2013-020-5/}
}
TY  - JOUR
AU  - Mukwembi, Simon
TI  - Size, Order, and Connected Domination
JO  - Canadian mathematical bulletin
PY  - 2014
SP  - 141
EP  - 144
VL  - 57
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-2013-020-5/
DO  - 10.4153/CMB-2013-020-5
ID  - 10_4153_CMB_2013_020_5
ER  - 
%0 Journal Article
%A Mukwembi, Simon
%T Size, Order, and Connected Domination
%J Canadian mathematical bulletin
%D 2014
%P 141-144
%V 57
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-2013-020-5/
%R 10.4153/CMB-2013-020-5
%F 10_4153_CMB_2013_020_5

[1] [1] Dankelmann, P. and Volkmann, L., Minimum size of a graph or digraph of given radius. Inform. Process. Lett. 109 (2009), no. 16, 971–973. Google Scholar | DOI

[2] [2] DeLaVina, E. and Waller, B., Spanning trees with many leaves and average distance. Electron. J. Combin. 15 (2008), no. 1, Research Paper 33. Google Scholar

[3] [3] Fernandes, L. M. and Gouveia, L. Minimal spanning trees with a constraint on the number of leaves. European J. Operational Research 104 (1998), 250–261. Google Scholar

[4] [4] Griggs, J. R., Kleitman, D. J., and Shastri, A. Spanning trees with many leaves in cubic graphs. J. Graph Theory 13 (1989), no. 6, 669–695. Google Scholar | DOI

[5] [5] Mantel, W., Problem 28, soln. by Gouventak, H., Mantel, W., J. Teixeira de Mattes, Schuh, F. and Wythoff, W. A.. Wiskundige Opgaven 10 (1907), 60–61. Google Scholar

[6] [6] Mukwembi, S. and Munyira, S., Radius, diameter and the leaf number. QuaesMath, t.. (submitted). Google Scholar

[7] [7] Ore, O., Diameters in graphs. J. Combin. Theory 5 (1968), 75–81. Google Scholar | DOI

[8] [8] Sanchis, L. A., On the number of edges of a graph with a given connected domination number. Discrete Math. 214 (2000), no. 1–3, 193–210. Google Scholar | DOI

[9] [9] Turán, P., On an extremal problem in graph theory. (Hungarian). Mat. és Fiz. Lapok 48 (1941), 436–452. Google Scholar

[10] [10] Vizing, V., The number of edges in a graph of given radius. Soviet Math. Dokl. 8 (1967), 535–536. Google Scholar

Cité par Sources :