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

DOI10.1016/J.DISC.2022.112996MaRDI QIDQ2144591zbMATH OpenOpenAlexFDO

Authors Zhenhua Lyu, Zejun Huang

Publication date 14 June 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

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: In this paper, we determine the maximum size of digraphs on $n$ vertices in which there are no two distinct walks of length $3$ with the same initial vertex and the same terminal vertex. The digraphs attaining this maximum size are also characterized. Combining this with previous results, we obtain a full solution to a problem proposed by X. Zhan in 2007.

Recommendations

• Extremal digraphs avoiding distinct walks of length 4 with the same endpoints
• A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints
• Extremal digraphs avoiding an orientation of the diamond
• Extremal digraphs whose walks with the same initial and terminal vertices have distinct lengths
• Digraphs that contain at most \(t\) distinct walks of a given length 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
• A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints
• A generalization of Turan's theorem to directed graphs
• Algorithmic Solution of Extremal Digraph Problems
• An extremal problem for some classes of oriented graphs
• Chemins Et Circuits Dans Les Graphes Orientes
• Digraphs that have at most one walk of a given length with the same endpoints
• Extremal digraphs avoiding an orientation of \(C_4\)
• Extremal digraphs avoiding an orientation of the diamond
• Extremal digraphs avoiding distinct walks of length 4 with the same endpoints
• Extremal problems for directed graphs
• Graph theory with applications
• Matrix theory
• On cycles and paths in digraphs
• On the 0-1 matrices whose squares are 0-1 matrices
• On the maximum number of arcs in some classes of graphs
• Subdivisions of transitive tournaments

Cited in

(7)

• Extremal digraphs avoiding an orientation of the diamond
• Extremal digraphs avoiding distinct walks of length 4 with the same endpoints
• Extremal digraphs avoiding an orientation of \(C_4\)
• 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
• Turán problems for \(k\)-geodetic digraphs
• A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints

This page was built for publication: Extremal digraphs avoiding distinct walks of length 3 with the same endpoints

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