Authors: Tuvi Etzion
Addresses: Department of Computer Science, Technion-Israel Institute of Technology, Haifa 32000, Israel
Abstract: 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.
Keywords: cages; forbidden subgraphs; Moore bound; Turán graphs; Turán's theorem.
International Journal of Information and Coding Theory, 2017 Vol.4 No.2/3, pp.145 - 158
Received: 25 Sep 2016
Accepted: 05 Oct 2016
Published online: 20 Apr 2017 *