Regular graphs with forbidden subgraphs of K_n with k edges

DOI10.1504/IJICOT.2017.10004704zbMATH Open1406.05049arXiv1509.03072OpenAlexW2963359425MaRDI QIDQ1664085FDOQ1664085

Tuvi Etzion

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 $dgeq3$, $ngeq3$, and $k$, where $$, 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 $3leqnleq5$.

Full work available at URL: https://arxiv.org/abs/1509.03072

zbMATH Keywords

Moore boundforbidden subgraphs[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Tur%EF%BF%BD%EF%BF%BDn+graphs&go=Go Tur��n graphs][https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Tur%EF%BF%BD%EF%BF%BDn%27s+theorem&go=Go Tur��n's theorem]cages

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Applications of graph theory to circuits and networks (94C15)

Cited In (3)

• Extremal regular graphs and hypergraphs related to fractional repetition codes
• Title not available (Why is that?)
• Pairs of forbidden class of subgraphs concerning K_1,3and P₆to have a cycle containing specified vertices

This page was built for publication: Regular graphs with forbidden subgraphs of \(K_n\) with \(k\) edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1664085)