Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
extremal problems; local property; locally tree; $k$-tree
extremal problems; local property; locally tree; $k$-tree
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$.
References:
[1] Borowiecki, M., Mihók, P.: On graphs with a local hereditary properties. Discrete Math. 236 (2001), 53-58. DOI 10.1016/S0012-365X(00)00430-1 | MR 1830598
[2] Bugata, P.: Trahtenbrot-Zykov problem and NP-completeness. Discrete Math. 108 (1992), 253-259. DOI 10.1016/0012-365X(92)90679-A | MR 1189848 | Zbl 0783.05076
[3] Bugata, P., Nagy, A., Vávra, R.: A polynomial time algorithm recognizing link trees. J. Graph Theory 19 (1995), 417-433. DOI 10.1002/jgt.3190190314 | MR 1324491
[4] Bulitko, V. K.: On graphs with prescribed links of vertices. Trudy Math. Inst. Steklova 133 (1973), 78-94. MR 0434882
[5] Chartrand, G., Lesniak, L.: Graphs and Digraphs, 2nd. Wadsworth & Brooks/Cole Monterey (1986). MR 0834583 | Zbl 0666.05001
[6] Erdős, P., Simonovits, M.: A limit theorem in graph theory. Studia Sci. Math. Hung. 1 (1966), 51-57. MR 0205876
[7] Fronček, D.: Locally linear graphs. Math. Slovaca 39 (1989), 3-6. MR 1016323
[8] Fronček, D.: Locally path-like graphs. Čas. Pěst. Mat. 114 (1989), 176-180. MR 1063763
[9] Fronček, D.: $e$-locally acyclic graphs. Applicationes Mathematicae 21 (1992), 437-440. DOI 10.4064/am-21-3-437-440 | MR 1178691
[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
[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 10.4064/am-19-3-4-497-503 | MR 0951365 | Zbl 0718.05022
[13] Kulkarni, K. H.: Sufficient conditions for edge-locally connected and $n$-connected graphs. Čas. Pěst. Mat. 106 (1981), 112-116. MR 0621175 | Zbl 0479.05043
[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 10.1137/0205021 | MR 0408312 | Zbl 0353.65019
[16] Ryjáček, Z.: $N_2$-locally disconnected graphs. Discrete Math. 121 (1993), 189-193. DOI 10.1016/0012-365X(93)90551-4 | MR 1246171
[17] Ryjáček, Z., Zelinka, B.: A locally disconnected graph with large number of edges. Math. Slovaca 37 (1987), 195-198. MR 0899435
[18] Sedláček, J.: Local properties of graphs. Čas. Pěst. Mat. 106 (1981), 290-298 Czech. MR 0629727
[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
[20] Seress, A., Szabó, T.: Dense graphs with cycle neighborhoods. J. Comb. Theory (B) 63 (1995), 281-293. DOI 10.1006/jctb.1995.1020 | MR 1320171
[21] Vanderjagt, D. W.: Graphs with prescribed local connectivities. Discrete Math. 10 (1974), 391-395. DOI 10.1016/0012-365X(74)90129-0 | MR 0357191 | Zbl 0293.05154
[22] Zelinka, B.: Locally tree-like graphs. Čas. Pěst. Mat. 108 (1983), 230-238. MR 0716406 | Zbl 0528.05040
[23] Zykov, A. A.: Problem 30. In: Theory of Graphs and Its Applications. Proc. Symp. Smolenice 1963 M. Fiedler Prague (1964), 164-165.
Search
Partner of
