Geodesic
On extremal sizes of locally $k$-tree graphs
Czechoslovak Mathematical Journal, Tome 60 (2010) no. 2, pp. 571-587 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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},
     year = {2010},
     volume = {60},
     number = {2},
     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
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
%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/

[1] Borowiecki, M., Mihók, P.: On graphs with a local hereditary properties. Discrete Math. 236 (2001), 53-58. | DOI | MR

[2] Bugata, P.: Trahtenbrot-Zykov problem and NP-completeness. Discrete Math. 108 (1992), 253-259. | DOI | MR | Zbl

[3] Bugata, P., Nagy, A., Vávra, R.: A polynomial time algorithm recognizing link trees. J. Graph Theory 19 (1995), 417-433. | DOI | MR

[4] Bulitko, V. K.: On graphs with prescribed links of vertices. Trudy Math. Inst. Steklova 133 (1973), 78-94. | MR

[5] Chartrand, G., Lesniak, L.: Graphs and Digraphs, 2nd. Wadsworth & Brooks/Cole Monterey (1986). | MR | Zbl

[6] Erdős, P., Simonovits, M.: A limit theorem in graph theory. Studia Sci. Math. Hung. 1 (1966), 51-57. | MR

[7] Fronček, D.: Locally linear graphs. Math. Slovaca 39 (1989), 3-6. | MR

[8] Fronček, D.: Locally path-like graphs. Čas. Pěst. Mat. 114 (1989), 176-180. | MR

[9] Fronček, D.: $e$-locally acyclic graphs. Applicationes Mathematicae 21 (1992), 437-440. | DOI | MR

[10] Hell, P.: Graphs with given neighbourhoods I. In: Problémes Combin. et Théorie des Graphes Colloq. Internat. CNRS 260 (1978), 219-223. | MR

[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.

[12] Kowalska, E.: On locally tree-like graphs. Applicationes Mathematicae 19 (1987), 497-503. | DOI | MR | Zbl

[13] Kulkarni, K. H.: Sufficient conditions for edge-locally connected and $n$-connected graphs. Čas. Pěst. Mat. 106 (1981), 112-116. | MR | Zbl

[14] Mantel, W.: Problem 28. Wiskundige Opgaven 10 (1907), 60-61.

[15] Rose, D. J., Tarjan, R. E., Lueker, G.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5 (1976), 266-283. | DOI | MR | Zbl

[16] Ryjáček, Z.: $N_2$-locally disconnected graphs. Discrete Math. 121 (1993), 189-193. | DOI | MR

[17] Ryjáček, Z., Zelinka, B.: A locally disconnected graph with large number of edges. Math. Slovaca 37 (1987), 195-198. | MR

[18] Sedláček, J.: Local properties of graphs. Čas. Pěst. Mat. 106 (1981), 290-298 Czech. | MR

[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. | MR

[20] Seress, A., Szabó, T.: Dense graphs with cycle neighborhoods. J. Comb. Theory (B) 63 (1995), 281-293. | DOI | MR

[21] Vanderjagt, D. W.: Graphs with prescribed local connectivities. Discrete Math. 10 (1974), 391-395. | DOI | MR | Zbl

[22] Zelinka, B.: Locally tree-like graphs. Čas. Pěst. Mat. 108 (1983), 230-238. | MR | Zbl

[23] Zykov, A. A.: Problem 30. In: Theory of Graphs and Its Applications. Proc. Symp. Smolenice 1963 M. Fiedler Prague (1964), 164-165.