Cite

In this short note we consider the oriented vertex Turán problem in the hypercube: for a fixed oriented graph F \vec F , determine the maximum cardinality exv(F,Qn) e{x_v}\left( {\vec F,{{\vec Q}_n}} \right) of a subset U of the vertices of the oriented hypercube Qn {\vec Q_n} such that the induced subgraph Qn[ U ] {\vec Q_n}\left[ U \right] does not contain any copy of F \vec F . We obtain the exact value of exv(Pk,Qn) e{x_v}\left( {\overrightarrow {{P_k},} \,\overrightarrow {{Q_n}} } \right) for the directed path Pk \overrightarrow {{P_k}} , the exact value of exv(V2,Qn) e{x_v}\left( {\overrightarrow {{V_2}} ,\,\overrightarrow {{Q_n}} } \right) for the directed cherry V2 \overrightarrow {{V_2}} and the asymptotic value of exv(T,Qn) e{x_v}\left( {\overrightarrow T ,\overrightarrow {{Q_n}} } \right) for any directed tree T \vec T .

eISSN:
2066-7752
Language:
English
Publication timeframe:
2 times per year
Journal Subjects:
Mathematics, General Mathematics