Title: Regular graphs with forbidden subgraphs of Kn with k edges

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.

DOI: 10.1504/IJICOT.2017.083835

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 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article