Back to Search
Start Over
Inducibility of directed paths
- Publication Year :
- 2018
- Publisher :
- arXiv, 2018.
-
Abstract
- A long standing open problem in extremal graph theory is to describe all graphs that maximize the number of induced copies of a path on four vertices. The character of the problem changes in the setting of oriented graphs, and becomes more tractable. Here we resolve this problem in the setting of oriented graphs without transitive triangles.<br />Comment: 17 pages, 4 figures
- Subjects :
- Discrete mathematics
Transitive relation
Open problem
020206 networking & telecommunications
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Extremal graph theory
Combinatorics
Character (mathematics)
010201 computation theory & mathematics
Path (graph theory)
0202 electrical engineering, electronic engineering, information engineering
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Combinatorics (math.CO)
Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....578908261129933ee87c7a5627ce7a3c
- Full Text :
- https://doi.org/10.48550/arxiv.1811.03747