Regular graphs with forbidden subgraphs of \(K_n\) with \(k\) edges
From MaRDI portal
Publication:1664085
DOI10.1504/IJICOT.2017.10004704zbMath1406.05049arXiv1509.03072OpenAlexW2963359425MaRDI QIDQ1664085
Publication date: 24 August 2018
Published in: International Journal of Information and Coding Theory (Search for Journal in Brave)
Abstract: In this paper we raise a variant of a classic problem in extremal graph theory, which is motivated by a design of fractional repetition codes, a model in distributed storage systems. For any feasible positive integers $dgeq 3$, $n geq 3$, and $k$, where $n-1 leq k leq �inom{n}{2}$, 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 also to provide some bounds for general values of $n$, $d$, and $k$. A few general bounds with some exact values, for this Tur'an-type problem, are given. We present an almost complete solution for $3 leq n leq 5$.
Full work available at URL: https://arxiv.org/abs/1509.03072
Extremal problems in graph theory (05C35) Applications of graph theory to circuits and networks (94C15)
Related Items (1)
This page was built for publication: Regular graphs with forbidden subgraphs of \(K_n\) with \(k\) edges
