# On extremal sizes of locally $k$-tree graphs

• Volume: 60, Issue: 2, page 571-587
• ISSN: 0011-4642

top

## Abstract

top
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 $\left(k+1\right)$-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 \left(n\right)$ and $O\left({n}^{2}\right)$, where both bounds are asymptotically tight. In contrast, the number of edges in an $n$-vertex $k$-tree is always linear in $n$.

## How to cite

top

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 -

## References

top
1. Borowiecki, M., Mihók, P., 10.1016/S0012-365X(00)00430-1, Discrete Math. 236 (2001), 53-58. (2001) MR1830598DOI10.1016/S0012-365X(00)00430-1
2. Bugata, P., 10.1016/0012-365X(92)90679-A, Discrete Math. 108 (1992), 253-259. (1992) Zbl0783.05076MR1189848DOI10.1016/0012-365X(92)90679-A
3. Bugata, P., Nagy, A., Vávra, R., 10.1002/jgt.3190190314, J. Graph Theory 19 (1995), 417-433. (1995) MR1324491DOI10.1002/jgt.3190190314
4. Bulitko, V. K., On graphs with prescribed links of vertices, Trudy Math. Inst. Steklova 133 (1973), 78-94. (1973) MR0434882
5. Chartrand, G., Lesniak, L., Graphs and Digraphs, 2nd, Wadsworth &amp; Brooks/Cole Monterey (1986). (1986) Zbl0666.05001MR0834583
6. Erdős, P., Simonovits, M., A limit theorem in graph theory, Studia Sci. Math. Hung. 1 (1966), 51-57. (1966) MR0205876
7. Fronček, D., Locally linear graphs, Math. Slovaca 39 (1989), 3-6. (1989) MR1016323
8. Fronček, D., Locally path-like graphs, Čas. Pěst. Mat. 114 (1989), 176-180. (1989) MR1063763
9. Fronček, D., 10.4064/am-21-3-437-440, Applicationes Mathematicae 21 (1992), 437-440. (1992) MR1178691DOI10.4064/am-21-3-437-440
10. Hell, P., Graphs with given neighbourhoods I, In: Problémes Combin. et Théorie des Graphes Colloq. Internat. CNRS 260 (1978), 219-223. (1978) MR0539979
11. Justel, C. M., Markenzon, L., Lexicographic breadth first search and $k$-trees, In: Proceedings of JIM'2000 Secondes Journées de l'Informatique Messine, Metz, France (2000), 23-28. (2000)
12. Kowalska, E., 10.4064/am-19-3-4-497-503, Applicationes Mathematicae 19 (1987), 497-503. (1987) Zbl0718.05022MR0951365DOI10.4064/am-19-3-4-497-503
13. Kulkarni, K. H., Sufficient conditions for edge-locally connected and $n$-connected graphs, Čas. Pěst. Mat. 106 (1981), 112-116. (1981) Zbl0479.05043MR0621175
14. Mantel, W., Problem 28, Wiskundige Opgaven 10 (1907), 60-61. (1907)
15. Rose, D. J., Tarjan, R. E., Lueker, G., 10.1137/0205021, SIAM J. Comput. 5 (1976), 266-283. (1976) Zbl0353.65019MR0408312DOI10.1137/0205021
16. Ryjáček, Z., 10.1016/0012-365X(93)90551-4, Discrete Math. 121 (1993), 189-193. (1993) MR1246171DOI10.1016/0012-365X(93)90551-4
17. Ryjáček, Z., Zelinka, B., A locally disconnected graph with large number of edges, Math. Slovaca 37 (1987), 195-198. (1987) MR0899435
18. Sedláček, J., Local properties of graphs, Čas. Pěst. Mat. 106 (1981), 290-298 Czech. (1981) MR0629727
19. Sedláček, J., On local properties of finite graphs, In: Graph Theory, Łagów 1981. LNM 1018 M. Borowiecki, J. W. Kennedy, M. M. Sysło Springer-Verlag New York-Berlin (1983), 242-247. (1983) MR0730654
20. Seress, A., Szabó, T., 10.1006/jctb.1995.1020, J. Comb. Theory (B) 63 (1995), 281-293. (1995) MR1320171DOI10.1006/jctb.1995.1020
21. Vanderjagt, D. W., 10.1016/0012-365X(74)90129-0, Discrete Math. 10 (1974), 391-395. (1974) Zbl0293.05154MR0357191DOI10.1016/0012-365X(74)90129-0
22. Zelinka, B., Locally tree-like graphs, Čas. Pěst. Mat. 108 (1983), 230-238. (1983) Zbl0528.05040MR0716406
23. Zykov, A. A., Problem 30, In: Theory of Graphs and Its Applications. Proc. Symp. Smolenice 1963 M. Fiedler Prague (1964), 164-165. (1964)

top

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.