DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

Z. Lyu

Zhenhua Lyu

Shenyang Aerospace University

email: lyuzhh@outlook.com

Title:

Extremal digraphs avoiding distinct walks of length 4 with the same endpoints

PDF

Source:

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:

  1. 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
  2. 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.
  3. 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
  4. 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
  5. 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
  6. 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
  7. X. Zhan, Matrix Theory, Grad. Stud. Math. 147 (Amer. Math. Soc., Providence, 2013).
    https://doi.org/10.1090/gsm/147

Close