Regular graphs with forbidden subgraphs of K_n with k edges

DOI10.1504/IJICOT.2017.10004704MaRDI QIDQ1664085zbMATH OpenOpenAlexFDO

Authors Tuvi Etzion

Publication date 24 August 2018

Published in International Journal of Information and Coding Theory (Search for Journal in Brave)

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

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)

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$.

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

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
• scientific article; zbMATH DE number 4187869 (Why is no real title available?)
• 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)