Vertex Turán problems for the oriented hypercube

Gerbner, Dániel and Methuku, Abhishek and Nagy, Dániel and Patkós, Balázs and Vizer, Máté (2020) Vertex Turán problems for the oriented hypercube. ACTA UNIVERSITATIS SAPIENTIAE MATHEMATICA. ISSN 1844-6094

Preview

Text 1807.pdf Available under License Creative Commons Attribution. Download (142kB) | Preview

Abstract

In this short note we consider the oriented vertex Turán problem in the hypercube: for a fixed oriented graph F→, determine the maximum size exv(F→,Qn−→) of a subset U of the vertices of the oriented hypercube Qn−→ such that the induced subgraph Qn−→[U] does not contain any copy of F→. We obtain the exact value of exv(Pk−→,Qn−→) for the directed path Pk−→, the exact value of exv(V2−→,Qn−→) for the directed cherry V2−→ and the asymptotic value of exv(T→,Qn−→) for any directed tree T→.

Actions (login required)

Edit Item