اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn Degree Properties of Crossing-Critical Families of Graphs
53
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Answering an open question from 2007, we construct infinite $k$-crossing-critical families of graphs that contain vertices of any prescribed odd degree, for any sufficiently large~$k$. To answer this question, we introduce several properties of infinite families of graphs and operations on the families allowing us to obtain new families preserving those properties. This conceptual setup allows us to answer general questions on behaviour of degrees in crossing-critical graphs: we show that, for any set of integers $D$ such that $min(D)geq 3$ and $3,4in D$, and for any sufficiently large $k$, there exists a $k$-crossing-critical family such that the numbers in $D$ are precisely the vertex degrees that occur arbitrarily often in (large enough) graphs of this family. Furthermore, even if both $D$ and some average degree in the interval $(3,6)$ are prescribed, $k$-crossing-critical families exist for any sufficiently large $k$.
قيم البحث
اقرأ أيضاً
ErdH{o}s posed the problem of finding conditions on a graph $G$ that imply the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We generalize this problem to general cases. Let $delt
a_r$ be the least number so that any graph $G$ on $n$ vertices with minimum degree $delta_rn$ has the property $P_{r-1}(G)=K_rf(G),$ where $P_{r-1}(G)$ is the largest number of edges in an $(r-1)$-partite subgraph and $K_rf(G)$ is the largest number of edges in a $K_r$-free subgraph. We show that $frac{3r-4}{3r-1}<delta_rlefrac{4(3r-7)(r-1)+1}{4(r-2)(3r-4)}$ when $rge4.$ In particular, $delta_4le 0.9415.$
The first known families of cages arised from the incidence graphs of generalized polygons of order $q$, $q$ a prime power. In particular, $(q+1,6)$--cages have been obtained from the projective planes of order $q$. Morever, infinite families of smal
l regular graphs of girth 5 have been constructed performing algebraic operations on $mathbb{F}_q$. In this paper, we introduce some combinatorial operations to construct new infinite families of small regular graphs of girth 7 from the $(q+1,8)$--cages arising from the generalized quadrangles of order $q$, $q$ a prime power.
In this paper we obtain $(q+3)$--regular graphs of girth 5 with fewer vertices than previously known ones for $q=13,17,19$ and for any prime $q ge 23$ performing operations of reductions and amalgams on the Levi graph $B_q$ of an elliptic semiplane o
f type ${cal C}$. We also obtain a 13-regular graph of girth 5 on 236 vertices from $B_{11}$ using the same technique.
A simple $n$-vertex graph has a prime vertex labeling if the vertices can be injectively labeled with the integers $1, 2, 3,ldots, n$ such that adjacent vertices have relatively prime labels. We will present previously unknown prime vertex labelings
for new families of graphs, all of which are special cases of Seoud and Youssefs conjecture that all unicyclic graphs have a prime labeling.
A simple and connected $n$-vertex graph has a prime vertex labeling if the vertices can be injectively labeled with the integers $1, 2, 3,ldots, n$, such that adjacent vertices have relatively prime labels. We will present previously unknown prime ve
rtex labelings for new families of graphs including cycle pendant stars, cycle chains, prisms, and generalized books.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
