On extremal sizes of locally $k$-tree graphs

Borowiecki, Mieczysław, et al. "On extremal sizes of locally $k$-tree graphs." Czechoslovak Mathematical Journal 60.2 (2010): 571-587. <http://eudml.org/doc/38028>.

@article{Borowiecki2010,
abstract = {A graph $G$ is a 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$.},
author = {Borowiecki, Mieczysław, Borowiecki, Piotr, Sidorowicz, Elżbieta, Skupień, Zdzisław},
journal = {Czechoslovak Mathematical Journal},
keywords = {extremal problems; local property; locally tree; $k$-tree; extremal problem; local property; locally tree; -tree},
language = {eng},
number = {2},
pages = {571-587},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On extremal sizes of locally $k$-tree graphs},
url = {http://eudml.org/doc/38028},
volume = {60},
year = {2010},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 60
IS - 2
SP - 571
EP - 587
AB - A graph $G$ is a 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$.
LA - eng
KW - extremal problems; local property; locally tree; $k$-tree; extremal problem; local property; locally tree; -tree
UR - http://eudml.org/doc/38028
ER -