Regular graphs with forbidden subgraphs of Kn with k edges. (2017)

• Record Type: Journal Article
• Authors: Etzion, Tuvi
• Is Part Of: International journal of information and coding theory. Volume 4:Number 2/3(2017)
• Page Start: 145
• Page End: 158
• Publication Date: 2017
• Subjects: cages -- forbidden subgraphs -- Moore bound -- Tur&amp -- #225 -- n graphs -- Tur&amp -- #225 -- n&amp -- #39 -- s theorem; Coding theory -- Periodicals; Information theory -- Periodicals; 003.54
• Languages: English
• ISSNs: 1753-7703

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.