Geodesic
On extremal sizes of locally $k$-tree graphs
Czechoslovak Mathematical Journal, Tome 60 (2010) no. 2, pp. 571-587

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

A graph $G$ is a {\it locally $k$-tree graph} if for any vertex $v$ the subgraph induced by the neighbours of $v$ is a $k$-tree, $k\ge 0$, where $0$-tree is an edgeless graph, $1$-tree is a tree. We characterize the minimum-size locally $k$-trees with $n$ vertices. The minimum-size connected locally $k$-trees are simply $(k+1)$-trees. For $k\ge 1$, we construct locally $k$-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an $n$-vertex locally $k$-tree graph is between $\Omega (n)$ and $O(n^2)$, where both bounds are asymptotically tight. In contrast, the number of edges in an $n$-vertex $k$-tree is always linear in $n$.
Classification : 05C05, 05C35
Keywords: extremal problems; local property; locally tree; $k$-tree 
@article{CMJ_2010__60_2_a20,
     author = {Borowiecki, Mieczys{\l}aw and Borowiecki, Piotr and Sidorowicz, El\.zbieta and Skupie\'n, Zdzis{\l}aw},
     title = {On extremal sizes of locally $k$-tree graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {571--587},
     publisher = {mathdoc},
     volume = {60},
     number = {2},
     year = {2010},
     mrnumber = {2657970},
     zbl = {1224.05246},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2010__60_2_a20/}
}
TY  - JOUR
AU  - Borowiecki, Mieczysław
AU  - Borowiecki, Piotr
AU  - Sidorowicz, Elżbieta
AU  - Skupień, Zdzisław
TI  - On extremal sizes of locally $k$-tree graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2010
SP  - 571
EP  - 587
VL  - 60
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMJ_2010__60_2_a20/
LA  - en
ID  - CMJ_2010__60_2_a20
ER  - 
%0 Journal Article
%A Borowiecki, Mieczysław
%A Borowiecki, Piotr
%A Sidorowicz, Elżbieta
%A Skupień, Zdzisław
%T On extremal sizes of locally $k$-tree graphs
%J Czechoslovak Mathematical Journal
%D 2010
%P 571-587
%V 60
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMJ_2010__60_2_a20/
%G en
%F CMJ_2010__60_2_a20
Borowiecki, Mieczysław; Borowiecki, Piotr; Sidorowicz, Elżbieta; Skupień, Zdzisław. On extremal sizes of locally $k$-tree graphs. Czechoslovak Mathematical Journal, Tome 60 (2010) no. 2, pp. 571-587. http://geodesic.mathdoc.fr/item/CMJ_2010__60_2_a20/