On density of subgraphs of Cartesian products
Victor D. Chepoi, Arnaud Labourel, Sébastien Ratel · Journal of Graph Theory · 2019
Abstract In this paper, we extend two classical results about the density of subgraphs of hypercubes to subgraphs of Cartesian products of arbitrary connected graphs. Namely, we show that , where is the maximum ratio taken over all subgraphs of . We introduce the notions of VC‐dimension and VC‐density of a subgraph of a Cartesian product , generalizing the classical Vapnik‐Chervonenkis dimension of set‐families (viewed as subgraphs of hypercubes). We prove that if belong to the class of all finite connected graphs not containing a given graph as a minor, then for any subgraph of the sharper inequality holds, where is the supremum of the densities of the graphs from . We refine and sharpen these two results to several specific graph classes. We also derive upper bounds (some of them polylogarithmic) for the size of adjacency labeling schemes of subgraphs of Cartesian products.