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

DOI10.1016/J.DISC.2022.112996zbMATH Open1491.05094arXiv2104.08498OpenAlexW3156831206MaRDI QIDQ2144591FDOQ2144591

Authors: Zhenhua Lyu, Zejun Huang 

Publication date: 14 June 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Matrix theory
• Graph theory with applications
• 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 avoiding distinct walks of length 4 with the same endpoints
• On the 0-1 matrices whose squares are 0-1 matrices
• Algorithmic Solution of Extremal Digraph Problems
• Title not available (Why is that?)
• Extremal problems for directed graphs
• Chemins Et Circuits Dans Les Graphes Orientes
• Title not available (Why is that?)
• A generalization of Turan's theorem to directed graphs
• On cycles and paths in digraphs
• Subdivisions of transitive tournaments
• Extremal digraphs avoiding an orientation of \(C_4\)
• 0-1 matrices whose \(k\)-th powers have bounded entries
• Extremal digraphs avoiding an orientation of the diamond
• An extremal problem for some classes of oriented graphs
• On the maximum number of arcs in some classes of graphs

Cited In (7)

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