×

Digraphs that contain at most \(t\) distinct walks of a given length with the same endpoints. (English) Zbl 1464.05162

Summary: Let \(n\), \(k\), \(t\) be positive integers. What is the maximum number of arcs in a digraph on \(n\) vertices in which there are at most \(t\) distinct walks of length \(k\) with the same endpoints? Determine the extremal digraphs attaining the maximum number. When \(t=1\), the problem has been studied by H. Wu [Linear Algebra Appl. 432, No. 11, 2909–2924 (2010; Zbl 1195.05016)], by Z. Huang and X. Zhan [Discrete Math. 311, No. 1, 70–79 (2011; Zbl 1225.05115)], by Z. Huang et al. [ibid. 342, No. 6, 1703–1717 (2019; Zbl 1414.05133)], by Z. Lyu [“Extremal digraphs avoiding distinct walks of length 4 with the same endpoints”, Discuss. Math., Graph Theory (to appear)] in four papers, and they solved all the cases but \(k=3\). For \(t\geq 2\), Huang and Lyu proved that the maximum number is equal to \(n(n-1)/2\) and the extremal digraph is the transitive tournament when \(n\ge 6t+2\) and \(k\ge n-1\). They also discussed the maximum number for the case \(n=k+2\), \(k+3\), \(k+4\). In this paper, we solve the problem for the case \(k\ge 6t+1\) and \(n\ge k+5\), and we also characterize the structures of the extremal digraphs for \(n=k+2\), \(k+3\), \(k+4\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C12 Distance in graphs
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, B., Extremal graph theory, Handbook of Combinatorics, 1231-1292 (1995), Amsterdam: Elsevier, Amsterdam · Zbl 0844.05054
[2] Brown, WG; Erdős, P.; Simonovits, M., Extremal problems for directed graphs, J Combin Theor Ser B, 15, 77-93 (1973) · Zbl 0253.05124
[3] Brown, WG; Erdős, P.; Simonovits, M., Algorithmic solution of extremal digraph problems, Trans Am Math Soc, 292, 421-449 (1985) · Zbl 0607.05040
[4] Brown, WG; Harary, F., Extremal digraphs, combinatorial theory and its applications, Colloq Math Soc Janos Bolyai, 4I, 135-198 (1970)
[5] Brown WG, Simonovits M (2002) Extremal multigraph and digraph problems, Paul Erdős and his mathematics, II (Budapest, 1999), 157-203, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest · Zbl 1029.05080
[6] Harary, F.; Moser, L., The theory of round robin tournaments, Am Math Mon, 73, 231-246 (1966) · Zbl 0142.41602
[7] Huang, Z.; Lyu, Z., 0-1 matrices whose \(k\)-th powers have bounded entries, Linear Multilinear Algebra, 68, 1972-1982 (2020) · Zbl 1455.15008
[8] Huang, Z.; Lyu, Z., Extremal digraphs avoiding an orientation of \(C_4\), Discrete Math, 343, 111827 (2020) · Zbl 1435.05093
[9] Huang, Z.; Lyu, Z.; Qiao, P., A Turán problem on digraphs avoiding different walks of a given length with the same endpoints, Discrete Math, 342, 1703-1717 (2019) · Zbl 1414.05133
[10] Huang, Z.; Zhan, X., Digraphs that have at most one walk of a given length with the same endpoints, Discrete Math, 311, 70-79 (2011) · Zbl 1225.05115
[11] Jacob H, Meyniel H (1983) Extension of Turán’s and Brooks’ theorems and new notions of stability and coloring in digraphs, Combinatorial Mathematics (Marseille-Luminy, 1981), 365-370, North-Holland Math. Stud., 75, Ann. Discrete Math., 17, North-Holland, Amsterdam · Zbl 0525.05027
[12] Lyu, Z., Extremal digraphs avoiding distinct walks of length 4 with the same endpoints, Discuss Math Graph Theor (2020)
[13] Maurer, SB; Rabinovitch, I.; Trotter, WT Jr, A generalization of Turans theorem to directed graphs, Discrete Math, 32, 167-189 (1980) · Zbl 0442.05029
[14] Reiman I, Uber ein Problem von K. Zarankiewicz, (1958) Acta Math Acad Sci Hungar 9(3-4):269-273
[15] Scott, AD, Subdivisions of transitive tournaments, Eur J Combin, 21, 1067-1071 (2000) · Zbl 0965.05049
[16] Simonovits M (1968) A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 279-319, Academic Press, New York
[17] Tait, M.; Timmons, C., Sidon sets and graphs without 4-cycles, J Comb, 5, 155-165 (2014) · Zbl 1304.05078
[18] Turán, P., Eine Extremalaufgabe aus der Graphentheorie, Mat Fiz Lapok, 48, 436-452 (1941) · Zbl 0026.26903
[19] Turán, P., On the theory of graphs, Colloq Math, 3, 19-30 (1954) · Zbl 0055.17004
[20] West D.B (1996) Introduction to Graph Theory. Prentice Hall, Inc.,
[21] Wu, H., On the 0-1 matrices whose squares are 0-1 matrices, Linear Algebra Appl, 432, 2909-2924 (2010) · Zbl 1195.05016
[22] Zhan, X., Matrix theory, graduate studies in mathematics 147 (2013), Providence, RI: American Mathematical Society, Providence, RI
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.