Regular graphs with forbidden subgraphs of K_n with k edges

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

Authors: 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

Recommendations

• scientific article; zbMATH DE number 4187869
• Regular subgraphs of uniform hypergraphs
• Regular Turán numbers of complete bipartite graphs
• Note on regular subgraphs
• Resolution of the Erdős–Sauer problem on regular subgraphs

zbMATH Keywords

Moore boundforbidden subgraphscagesTurán's theoremTurán graphs

Mathematics Subject Classification ID

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

Cited In (5)

• Extremal regular graphs and hypergraphs related to fractional repetition codes
• Codes for distributed storage from 3-regular graphs
• Investigating the existence and the regularity of logarithmic Harary graphs
• 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)