×

Regular graphs with forbidden subgraphs of \(K_n\) with \(k\) edges. (English) Zbl 1406.05049

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\).

MSC:

05C35 Extremal problems in graph theory
94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI arXiv