| Title:
|
On extremal sizes of locally $k$-tree graphs (English) |
| Author:
|
Borowiecki, Mieczysław |
| Author:
|
Borowiecki, Piotr |
| Author:
|
Sidorowicz, Elżbieta |
| Author:
|
Skupień, Zdzisław |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
60 |
| Issue:
|
2 |
| Year:
|
2010 |
| Pages:
|
571-587 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
extremal problems |
| Keyword:
|
local property |
| Keyword:
|
locally tree |
| Keyword:
|
$k$-tree |
| MSC:
|
05C05 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 1224.05246 |
| idMR:
|
MR2657970 |
| . |
| Date available:
|
2010-07-20T17:00:38Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140590 |
| . |
| Reference:
|
[1] Borowiecki, M., Mihók, P.: On graphs with a local hereditary properties.Discrete Math. 236 (2001), 53-58. MR 1830598, 10.1016/S0012-365X(00)00430-1 |
| Reference:
|
[2] Bugata, P.: Trahtenbrot-Zykov problem and NP-completeness.Discrete Math. 108 (1992), 253-259. Zbl 0783.05076, MR 1189848, 10.1016/0012-365X(92)90679-A |
| Reference:
|
[3] Bugata, P., Nagy, A., Vávra, R.: A polynomial time algorithm recognizing link trees.J. Graph Theory 19 (1995), 417-433. MR 1324491, 10.1002/jgt.3190190314 |
| Reference:
|
[4] Bulitko, V. K.: On graphs with prescribed links of vertices.Trudy Math. Inst. Steklova 133 (1973), 78-94. MR 0434882 |
| Reference:
|
[5] Chartrand, G., Lesniak, L.: Graphs and Digraphs, 2nd.Wadsworth & Brooks/Cole Monterey (1986). Zbl 0666.05001, MR 0834583 |
| Reference:
|
[6] Erdős, P., Simonovits, M.: A limit theorem in graph theory.Studia Sci. Math. Hung. 1 (1966), 51-57. MR 0205876 |
| Reference:
|
[7] Fronček, D.: Locally linear graphs.Math. Slovaca 39 (1989), 3-6. MR 1016323 |
| Reference:
|
[8] Fronček, D.: Locally path-like graphs.Čas. Pěst. Mat. 114 (1989), 176-180. MR 1063763 |
| Reference:
|
[9] Fronček, D.: $e$-locally acyclic graphs.Applicationes Mathematicae 21 (1992), 437-440. MR 1178691, 10.4064/am-21-3-437-440 |
| Reference:
|
[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 0539979 |
| Reference:
|
[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. |
| Reference:
|
[12] Kowalska, E.: On locally tree-like graphs.Applicationes Mathematicae 19 (1987), 497-503. Zbl 0718.05022, MR 0951365, 10.4064/am-19-3-4-497-503 |
| Reference:
|
[13] Kulkarni, K. H.: Sufficient conditions for edge-locally connected and $n$-connected graphs.Čas. Pěst. Mat. 106 (1981), 112-116. Zbl 0479.05043, MR 0621175 |
| Reference:
|
[14] Mantel, W.: Problem 28.Wiskundige Opgaven 10 (1907), 60-61. |
| Reference:
|
[15] Rose, D. J., Tarjan, R. E., Lueker, G.: Algorithmic aspects of vertex elimination on graphs.SIAM J. Comput. 5 (1976), 266-283. Zbl 0353.65019, MR 0408312, 10.1137/0205021 |
| Reference:
|
[16] Ryjáček, Z.: $N_2$-locally disconnected graphs.Discrete Math. 121 (1993), 189-193. MR 1246171, 10.1016/0012-365X(93)90551-4 |
| Reference:
|
[17] Ryjáček, Z., Zelinka, B.: A locally disconnected graph with large number of edges.Math. Slovaca 37 (1987), 195-198. MR 0899435 |
| Reference:
|
[18] Sedláček, J.: Local properties of graphs.Čas. Pěst. Mat. 106 (1981), 290-298 Czech. MR 0629727 |
| Reference:
|
[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 0730654 |
| Reference:
|
[20] Seress, A., Szabó, T.: Dense graphs with cycle neighborhoods.J. Comb. Theory (B) 63 (1995), 281-293. MR 1320171, 10.1006/jctb.1995.1020 |
| Reference:
|
[21] Vanderjagt, D. W.: Graphs with prescribed local connectivities.Discrete Math. 10 (1974), 391-395. Zbl 0293.05154, MR 0357191, 10.1016/0012-365X(74)90129-0 |
| Reference:
|
[22] Zelinka, B.: Locally tree-like graphs.Čas. Pěst. Mat. 108 (1983), 230-238. Zbl 0528.05040, MR 0716406 |
| Reference:
|
[23] Zykov, A. A.: Problem 30.In: Theory of Graphs and Its Applications. Proc. Symp. Smolenice 1963 M. Fiedler Prague (1964), 164-165. |
| . |
