Regular graphs with forbidden subgraphs of \(K_n\) with \(k\) edges (Q1664085)

Summary: In this paper, we raise a variant of a classic problem in an extremal graph theory, which is motivated by a design of fractional repetition codes, a model in distributed storage systems. For any feasible positive integers \(d>2\), \(n>2\) and \(k\), what is the minimum possible number of vertices in a \(d\)-regular undirected graph whose subgraphs with \(n\) vertices contain at most \(k\) edges? The goal of this paper is to give the exact number of vertices for each instance of the problem and to provide some bounds for general values of \(n\), \(d\) and \(k\). A few general bounds with some exact values, for this Turán-type problem, are given. We present an almost complete solution for \(2<n<6\).