A note on extremal digraphs containing at most t walks of length k with the same endpoints

DOI10.1007/S00373-021-02449-9MaRDI QIDQ2115146zbMATH OpenOpenAlexFDO

Authors Zhenhua Lyu

Publication date 15 March 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.00212

zbMATH Keywords

digraphwalkTurán problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

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? In this paper, we prove that the maximum number is equal to $n(n-1)/2$ and the extremal digraph are the transitive tournaments when $kgen-1gemax2t+1,2leftlceilsqrt2t+9/4+1/2ightceil+3$. Based on this result, we may determine the maximum numbers and the extremal digraphs for $kgemax2t+1,2leftlceilsqrt2t+9/4+1/2ightceil+3$ and $n$ is sufficiently large, which generalises the existing results. A conjecture is also presented.

Recommendations

• Digraphs that contain at most \(t\) distinct walks of a given length with the same endpoints
• Digraphs that have at most one walk of a given length with the same endpoints
• A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints
• Extremal digraphs whose walks with the same initial and terminal vertices have distinct lengths
• Extremal digraphs avoiding distinct walks of length 4 with the same endpoints

Cites work

• scientific article; zbMATH DE number 1943959 (Why is no real title available?)
• scientific article; zbMATH DE number 3333210 (Why is no real title available?)
• 0-1 matrices whose \(k\)-th powers have bounded entries
• 0-1 matrices whose squares have bounded entries
• A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints
• Digraphs that contain at most \(t\) distinct walks of a given length with the same endpoints
• Digraphs that have at most one walk of a given length with the same endpoints
• Extremal problems for directed graphs
• Graph theory with applications
• Matrix theory
• On the 0-1 matrices whose squares are 0-1 matrices

Cited in

(6)

• Extremal digraphs whose walks with the same initial and terminal vertices have distinct lengths
• Digraphs that have at most one walk of a given length with the same endpoints
• A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints
• Digraphs that contain at most \(t\) distinct walks of a given length with the same endpoints
• Extremal digraphs avoiding distinct walks of length 4 with the same endpoints
• \(\text{TT}_n\)-maximal digraphs of the minimum size

This page was built for publication: A note on extremal digraphs containing at most \(t\) walks of length \(k\) with the same endpoints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115146)