Graphs with constant links and induced Turán numbers

A graph G of constant link L is a graph in which the neighborhood of any vertex induces a graph isomorphic to L . Given two different graphs, H and G , the induced Turán number ex ( n ; H , G -ind ) is defined as the maximum number of edges in an n -vertex graph having no subgraph isomorphic to H and no copy from G as an induced subgraph. Our main motivation in this paper is to establish a bridge between graphs with constant link and induced Turán numbers via the class of t -regular, k -uniform (linear) hypergraphs of girth at least 4, as well as to present several methods of constructing connected graphs with constant link. We show that, for integers t ≥ 3 and k ≥ 3 , ex ( n ; C k , K 1 , t -ind ) ≤ ( k − 2 ) ( t − 1 ) n / 2 and that equality holds for infinitely many values of n . This result is built upon the existence of graphs with constant link tL with restricted cycle length, which we prove in another theorem. More precisely, we show that, given a graph F with constant link L and circumference c , then, for all integers t ≥ 2 and g > c , there exists a graph with constant link tL which is free of cycles of length l , for all c < l < g . We provide two proofs of this result using distinct approaches. We further present constructions of graphs with constant links tL , t ≥ 2 , and restricted cycle length based on Steiner Systems. Finally, starting from a connected graph of constant link tL , for t ≥ 2 , having order n and restricted cycle lengths, we provide a method to construct an infinite collection of connected graphs of constant link tL that preserves the cycle length restriction, and whose orders form an arithmetic progression qn , q ≥ 1 .