Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Digraphs that contain at most t distinct walks of a given length with the same endpoints

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

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 Wu, by Huang and Zhan, by Huang, Lyu and Qiao, by Lyu in four papers, and they solved all the cases but \(k=3\). For \(t\ge 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\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  • Bollobás B (1995) Extremal graph theory, Handbook of Combinatorics, vol 2. Elsevier, Amsterdam, pp 1231–1292

    MATH  Google Scholar 

  • Brown WG, Erdős P, Simonovits M (1973) Extremal problems for directed graphs. J Combin Theor Ser B 15:77–93

    Article  MathSciNet  Google Scholar 

  • Brown WG, Erdős P, Simonovits M (1985) Algorithmic solution of extremal digraph problems. Trans Am Math Soc 292:421–449

    Article  MathSciNet  Google Scholar 

  • Brown WG, Harary F (1970) Extremal digraphs, combinatorial theory and its applications. Colloq Math Soc Janos Bolyai 4I:135–198

    Google Scholar 

  • 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

  • Harary F, Moser L (1966) The theory of round robin tournaments. Am Math Mon 73:231–246

    Article  MathSciNet  Google Scholar 

  • Huang Z, Lyu Z (2020) 0–1 matrices whose \(k\)-th powers have bounded entries. Linear Multilinear Algebra 68:1972–1982

    Article  MathSciNet  Google Scholar 

  • Huang Z, Lyu Z (2020) Extremal digraphs avoiding an orientation of \(C_4\). Discrete Math 343:111827

    Article  MathSciNet  Google Scholar 

  • Huang Z, Lyu Z, Qiao P (2019) A Turán problem on digraphs avoiding different walks of a given length with the same endpoints. Discrete Math 342:1703–1717

    Article  MathSciNet  Google Scholar 

  • Huang Z, Zhan X (2011) Digraphs that have at most one walk of a given length with the same endpoints. Discrete Math 311:70–79

    Article  MathSciNet  Google Scholar 

  • 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

  • Lyu Z (2020) Extremal digraphs avoiding distinct walks of length 4 with the same endpoints. Discuss Math Graph Theor. https://doi.org/10.7151/dmgt.2321

    Article  Google Scholar 

  • Maurer SB, Rabinovitch I, Trotter WT Jr (1980) A generalization of Turans theorem to directed graphs. Discrete Math 32:167–189

    Article  MathSciNet  Google Scholar 

  • Reiman I, Uber ein Problem von K. Zarankiewicz, (1958) Acta Math Acad Sci Hungar 9(3–4):269–273

  • Scott AD (2000) Subdivisions of transitive tournaments. Eur J Combin 21:1067–1071

    Article  MathSciNet  Google Scholar 

  • 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

  • Tait M, Timmons C (2014) Sidon sets and graphs without 4-cycles. J Comb 5:155–165

    MathSciNet  MATH  Google Scholar 

  • Turán P (1941) Eine Extremalaufgabe aus der Graphentheorie. Mat Fiz Lapok 48:436–452

    MathSciNet  MATH  Google Scholar 

  • Turán P (1954) On the theory of graphs. Colloq Math 3:19–30

    Article  MathSciNet  Google Scholar 

  • West D.B (1996) Introduction to Graph Theory. Prentice Hall, Inc.,

  • Wu H (2010) On the 0–1 matrices whose squares are 0–1 matrices. Linear Algebra Appl 432:2909–2924

    Article  MathSciNet  Google Scholar 

  • Zhan X (2013) Matrix theory, graduate studies in mathematics 147. American Mathematical Society, Providence, RI

    Google Scholar 

Download references

Acknowledgements

The author is grateful to two anonymous referees whose comments helped to improve the presentation of this paper.

Author information

Authors and Affiliations

  1. School of Science, Shenyang Aerospace University, Shenyang, 110136, People’s Republic of China

    Zhenhua Lyu

Authors
  1. Zhenhua Lyu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhenhua Lyu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lyu, Z. Digraphs that contain at most t distinct walks of a given length with the same endpoints. J Comb Optim 41, 762–779 (2021). https://doi.org/10.1007/s10878-021-00718-0

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-021-00718-0

Keywords

Mathematics Subject Classification

Search

Navigation