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

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

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

digraph[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Tur%EF%BF%BD%EF%BF%BDn+problem&go=Go Tur��n problem]walk

Mathematics Subject Classification ID

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

Cites Work

• Matrix theory
• Title not available (Why is that?)
• 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 (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)