ترجمه فارسی مقاله نمودارهایی با پیوندهای ثابت و شماره های Turán القا شده

چکیده

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 ${\rm ex}(n; H, G{\rm -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 \geq 3$ and $k \geq 3$, ${\rm ex}(n; C_k, K_{1,t}{\rm -ind}) \leq (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 \geq 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 \geq 2$, and restricted cycle length based on Steiner Systems. Finally, starting from a connected graph of constant link $tL$, for $t \geq 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 \geq 1$.

چکیده به فارسی (ترجمه ماشینی)

نمودار $ g $ پیوند ثابت $ L $ نمادی است که در آن محله هر راس یک نمودار نمودار را به $ L $ القا می کند.با توجه به دو نمودار مختلف ، $ H $ و $ g $ ، شماره Turán القا شده $ {\ rm ex} (n ؛ h ، g {\ rm -ind}) $ به عنوان حداکثر تعداد لبه ها در $ n $ تعریف شده است-نمودار Vertex که دارای زیرگراف ایزومورفیک تا $ H $ و بدون نسخه از $ g $ به عنوان یک زیرگراف القا شده است.انگیزه اصلی ما در این مقاله ایجاد پلی بین نمودارها با پیوند ثابت و اعداد Turán القا شده از طریق کلاس $ t $ -regular ، $ k $ -inuform (خطی) Hypergraphs حداقل 4 $ $ و همچنین بهچندین روش برای ساخت نمودارهای متصل با پیوند ثابت ارائه دهید.ما نشان می دهیم که ، برای عدد صحیح $ t \ geq 3 $ و $ k \ geq 3 $ ، $ {\ rm ex} (n ؛ c_k ، k_ {1 ، t} {\ rm -ind}) \ leq (k – 2) (t – 1) n/2 $ و آن برابری برای مقادیر بی نهایت بسیاری از $ n $ را در خود جای داده است.این نتیجه بر اساس وجود نمودارها با پیوند ثابت $ tl $ با طول چرخه محدود ساخته شده است ، که ما در یک قضیه دیگر اثبات می کنیم.به طور دقیق تر ، ما نشان می دهیم که با توجه به یک نمودار $ f $ با پیوند ثابت $ l $ و دور $ c $ ، سپس ، برای همه عدد صحیح $ t \ geq 2 $ و $ g> c $ ، یک نمودار با پیوند ثابت وجود دارد$ tl $ که عاری از چرخه طول $ L $ است ، برای تمام $ c