Article in volume
Authors:
Title:
Extremal digraphs avoiding distinct walks of length 4 with the same endpoints
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 985-1004
Received: 2019-11-20 , Revised: 2020-03-30 , Accepted: 2020-03-30 , Available online: 2020-05-01 , https://doi.org/10.7151/dmgt.2321
Abstract:
Let $n\ge 8$ be an integer. We characterize the extremal digraphs of order $n$
with the maximum number of arcs avoiding distinct walks of length 4 with the
same endpoints.
Keywords:
digraph, Turán problems, transitive tournament, walk
References:
- W.G. Brown, P. Erdős and M. Simonovits, Extremal problems for directed graphs, J. Combin. Theory Ser. B 15 (1973) 77–93.
https://doi.org/10.1016/0095-8956(73)90034-8 - W.G. Brown and F. Harary, Extremal digraphs, in: Combinatorial Theory and its Applications, I, Colloq. Math. Soc. J. Bolyai 4, (North-Holland, Amsterdam 1970) 135–198.
- Z. Huang and Z. Lyu, $0-1$ matrices whose $k$-th powers have bounded entries, Linear Multilinear Algebra 68 (2020) 1972–1982.
https://doi.org/10.1080/03081087.2019.1567671 - Z. Huang, Z. Lyu and P. Qiao, A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints, Discrete Math. 342 (2019) 1703–1717.
https://doi.org/10.1016/j.disc.2019.02.002 - Z. Huang and X. Zhan, Digraphs that have at most one walk of a given length with the same endpoints, Discrete Math. 311 (2011) 70–79.
https://doi.org/10.1016/j.disc.2010.09.025 - H. Wu, On the $0-1$ matrices whose squares are $0-1$ matrices, Linear Algebra Appl. 432 (2010) 2909–2924.
https://doi.org/10.1016/j.laa.2009.12.033 - X. Zhan, Matrix Theory, Grad. Stud. Math. 147 (Amer. Math. Soc., Providence, 2013).
https://doi.org/10.1090/gsm/147
Close