×

On extremal sizes of locally \(k\)-tree graphs. (English) Zbl 1224.05246

Summary: 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\geq 0\), where a \(0\)-tree is an edgeless graph and a \(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\geq 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\).

MSC:

05C35 Extremal problems in graph theory
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] M. Borowiecki, P. Mihók: On graphs with a local hereditary properties. Discrete Math. 236 (2001), 53–58. · Zbl 0995.05126 · doi:10.1016/S0012-365X(00)00430-1
[2] P. Bugata: Trahtenbrot-Zykov problem and NP-completeness. Discrete Math. 108 (1992), 253–259. · Zbl 0783.05076 · doi:10.1016/0012-365X(92)90679-A
[3] P. Bugata, A. Nagy, R. Vávra: A polynomial time algorithm recognizing link trees. J. Graph Theory 19 (1995), 417–433. · Zbl 0819.05047 · doi:10.1002/jgt.3190190314
[4] V. K. Bulitko: On graphs with prescribed links of vertices. Trudy Math. Inst. Steklova 133 (1973), 78–94.
[5] G. Chartrand, L. Lesniak: Graphs and Digraphs, 2nd. Wadsworth & Brooks/Cole, Monterey, 1986. · Zbl 0666.05001
[6] P. Erdos, M. Simonovits: A limit theorem in graph theory. Studia Sci. Math. Hung. 1 (1966), 51–57.
[7] D. Fronček: Locally linear graphs. Math. Slovaca 39 (1989), 3–6. · Zbl 0664.05054
[8] D. Fronček: Locally path-like graphs. Čas. Pěst. Mat. 114 (1989), 176–180. · Zbl 0681.05043
[9] D. Fronček: e-locally acyclic graphs. Applicationes Mathematicae 21 (1992), 437–440.
[10] P. Hell: Graphs with given neighbourhoods I. In: Problémes Combin. et Théorie des Graphes. vol. 260, Colloq. Internat. CNRS, 1978, pp. 219–223.
[11] C. M. Justel, L. Markenzon: Lexicographic breadth first search and k-trees. In: Proceedings of JIM’2000 Secondes Journees de l’Informatique Messine, Metz, France. 2000, pp. 23–28.
[12] E. Kowalska: On locally tree-like graphs. Applicationes Mathematicae 19 (1987), 497–503. · Zbl 0718.05022
[13] K.H. Kulkarni: Sufficient conditions for edge-locally connected and n-connected graphs. Čas. Pěst. Mat. 106 (1981), 112–116. · Zbl 0479.05043
[14] W. Mantel: Problem 28. Wiskundige Opgaven 10 (1907), 60–61.
[15] D. J. Rose, R. E. Tarjan, G. Lueker: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5 (1976), 266–283. · Zbl 0353.65019 · doi:10.1137/0205021
[16] Z. Ryjáček: N 2-locally disconnected graphs. Discrete Math. 121 (1993), 189–193. · Zbl 0786.05092 · doi:10.1016/0012-365X(93)90551-4
[17] Z. Ryjáček, B. Zelinka: A locally disconnected graph with large number of edges. Math. Slovaca 37 (1987), 195–198.
[18] J. Sedláček: Local properties of graphs. Čas. Pěst. Mat. 106 (1981), 290–298. (In Czech.)
[19] J. Sedláček: On local properties of finite graphs. In: Graph Theory, Łagów 1981. LNM 1018 (M. Borowiecki, J.W. Kennedy, M.M. Sysło, eds.). Springer-Verlag, New York-Berlin, 1983, pp. 242–247.
[20] A. Seress, T. Szabó: Dense graphs with cycle neighborhoods. J. Comb. Theory (B) 63 (1995), 281–293. · Zbl 0820.05036 · doi:10.1006/jctb.1995.1020
[21] D.W. Vanderjagt: Graphs with prescribed local connectivities. Discrete Math. 10 (1974), 391–395. · Zbl 0293.05154 · doi:10.1016/0012-365X(74)90129-0
[22] B. Zelinka: Locally tree-like graphs. Čas. Pěst. Mat. 108 (1983), 230–238. · Zbl 0528.05040
[23] A.A. Zykov: Problem 30. In: Theory of Graphs and Its Applications. Proc. Symp. Smolenice 1963 (M. Fiedler, ed.). Prague, 1964, pp. 164–165.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.