Abstract
In this short note we consider the oriented vertex Turán problem in the hypercube: for a fixed oriented graph F→ v F, determine the maximum cardinality exv(F→,Q→n) e x v (v F,v Q n) of a subset U of the vertices of the oriented hypercube Q→n v Qn such that the induced subgraph Q→n[U] v Qn[U] does not contain any copy of F→ v F. We obtain the exact value of exv(Pk,→ Qn→) e xv(Pk Qn) for the directed path Pk→ Pk, the exact value of exv(V2→, Qn→) exv(V2 Qn) for the directed cherry V2→ V2 and the asymptotic value of exv(T→,Qn→) e xv T, Qn) for any directed tree T→ v T.
Original language | English (US) |
---|---|
Pages (from-to) | 356-366 |
Number of pages | 11 |
Journal | Acta Universitatis Sapientiae, Mathematica |
Volume | 13 |
Issue number | 2 |
DOIs | |
State | Published - Dec 1 2021 |
Externally published | Yes |
Keywords
- Extremal set theory
- Hypercube
- Vertex Turán
ASJC Scopus subject areas
- General Mathematics