ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.01
https://doi.org/10.26493/1855-3974.3109.e4b
(Also available at http://amc-journal.eu)
Connected Turán number of trees
Yair Caro
Department of Mathematics, University of Haifa-Oranim, Israel
Balázs Patkós *
HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Zsolt Tuza †
HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary and
University of Pannonia, Veszprém, Hungary
Received 24 April 2023, accepted 18 September 2023, published online 23 September 2024
Abstract
The connected Turán number is a variant of the much studied Turán number, ex(n, F ),
the largest number of edges that an n-vertex F -free graph may contain. We start a system-
atic study of the connected Turán number exc(n, F ), the largest number of edges that an
n-vertex connected F -free graph may contain. We focus on the case where the forbidden
graph is a tree. Prior to our work, exc(n, T ) was determined only for the case T is a star
or a path. Our main contribution is the determination of the exact value of exc(n, T ) for
small trees, in particular for all trees with at most six vertices, as well as some trees on
seven vertices and several infinite families of trees. We also collect several lower-bound
constructions of connected T -free graphs based on different graph parameters.
The celebrated conjecture of Erdős and Sós states that for any tree T , we have
ex(n, T ) ≤ (|T | − 2)n2 . We address the problem how much smaller exc(n, T ) can be,
what is the smallest possible ratio of exc(n, T ) and (|T | − 2)n2 as |T | grows.
Keywords: Extremal graph theory, connected host graphs, trees.
Math. Subj. Class. (2020): 05C35
*Corresponding author. Partially supported by NKFIH grants SNN 129364 and FK 132060.
†Partially supported by NKFIH grant SNN 129364.
E-mail addresses: yacaro@kvgeva.org.il (Yair Caro), patkos@renyi.hu (Balázs Patkós),
tuza.zsolt@mik.uni-pannon.hu (Zsolt Tuza)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.01
https://doi.org/10.26493/1855-3974.3109.e4b
(Dostopno tudi na http://amc-journal.eu)
Povezano Turánovo število dreves
Yair Caro
Department of Mathematics, University of Haifa-Oranim, Israel
Balázs Patkós *
HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Zsolt Tuza †
HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary and
University of Pannonia, Veszprém, Hungary
Prejeto 24. aprila 2023, sprejeto 18. septembra 2023, objavljeno na spletu 23. septembra 2024
Povzetek
Povezano Turánovo število je varianta zelo raziskanega Turánovega števila, ex(n, F ),
največjega števila povezav, ki jih lahko vsebuje n-točkovni F -prost graf. Začeli smo sis-
tematično preučevanje povezanega Turánovega števila exc(n, F ), največjega števila po-
vezav, ki jih lahko vsebuje povezan graf na n točkah brez F . Osredotočamo se na primer,
ko je prepovedani graf drevo. Pred našim delom je bil exc(n, T ) določen le za primer, ko
je T zvezda ali pot. Naš glavni prispevek je določitev natančne vrednosti exc(n, T ) za maj-
hna drevesa, zlasti za vsa drevesa z največ šestimi točkami, pa tudi za nekatera drevesa s
sedmimi točkami in več neskončnih družin dreves. Zberemo tudi več konstrukcij spodnjih
meja povezanih grafov brez T , ki temeljijo na različnih parametrih grafov.
Slavna domneva Erdősa in Sósa pravi, da za vsako drevo T velja
ex(n, T ) ≤ (|T | − 2)n2 . Ukvarjamo se s problemom, koliko manjše je lahko število
exc(n, T ), kakšno je najmanjše možno razmerje med exc(n, T ) in (|T | − 2)n2 , ko |T |
raste.
Ključne besede: Ekstremalna teorija grafov, povezani gostiteljski grafi, drevesa.
Math. Subj. Class. (2020): 05C35
*Kontaktni avtor. Delno podprt z NKFIH dotacijama SNN 129364 in FK 132060.
†Delno podprt z NKFIH dotacijo SNN 129364.
E-poštni naslovi: yacaro@kvgeva.org.il (Yair Caro), patkos@renyi.hu (Balázs Patkós),
tuza.zsolt@mik.uni-pannon.hu (Zsolt Tuza)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/