On Turán problems for Cartesian products of graphs

DOI10.1002/JCD.21651MaRDI QIDQ5205490zbMATH OpenOpenAlexFDO

Authors Alexander Sidorenko

Publication date 12 December 2019

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.01581

zbMATH Keywords

4-graphsTurán-type problemsTurán numbers

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Let $A,B$ be disjoint sets of sizes $n$ and $m$. Let $mathcalQ$ be a family of quadruples, having $2$ elements from $A$ and $2$ from $B$, such that any subset $SsubseteqAcupB$ with $|S|=7$, $|ScapA|geq2$ and $|ScapB|geq2$ contains one of the quadruples. We prove that the smallest size of $mathcalQ$ is $(1/16+O(1/n)+O(1/m))n^2{m}^2$ as $n,moinfty$. We also solve asymptotically a more general two-partite Tur'{a}n problem for quadruples.

Recommendations

• scientific article; zbMATH DE number 4214052
• scientific article; zbMATH DE number 739124
• On a problem of P. Turan concerning graphs
• On the gonality of Cartesian products of graphs
• scientific article; zbMATH DE number 3224335
• On the total domination number of Cartesian products of graphs
• Cartesian product graphs and \(k\)-tuple total domination
• On total domination in the Cartesian product of graphs
• scientific article; zbMATH DE number 1439495

Cited in

(3)

• Graph products and new solutions to Oberwolfach problems
• scientific article; zbMATH DE number 4214052 (Why is no real title available?)
• Turán Problems and Shadows III: Expansions of Graphs

This page was built for publication: On Turán problems for Cartesian products of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205490)