اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدQuintic graphs with every edge in a triangle
371
0
0.0
(
0
)
تأليف
James Preen
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We characterise the quintic (i.e. 5-regular) multigraphs with the property that every edge lies in a triangle. Such a graph is either from a set of small graphs or is formed by adding a perfect matching to a line graph of a cubic graph as double edges, or can be reduced by a sequence of operations to one of these graphs.
قيم البحث
اقرأ أيضاً
Considering regular graphs with every edge in a triangle we prove lower bounds for the number of triangles in such graphs. For r-regular graphs with r <= 5 we exhibit families of graphs with exactly that number of triangles and then classify all such
graphs using line graphs and even cycle decompositions. Examples of ways to create such r-regular graphs with r >= 6 are also given. In the 5-regular case, these minimal graphs are proven to be the only regular graphs with every edge in a triangle which cannot have an edge removed and still have every edge in a triangle.
For all $nge 9$, we show that the only triangle-free graphs on $n$ vertices maximizing the number $5$-cycles are balanced blow-ups of a 5-cycle. This completely resolves a conjecture by ErdH{o}s, and extends results by Grzesik and Hatami, Hladky, Kr{
a}l, Norin and Razborov, where they independently showed this same result for large $n$ and for all $n$ divisible by $5$.
Switches are operations which make local changes to the edges of a graph, usually with the aim of preserving the vertex degrees. We study a restricted set of switches, called triangle switches. Each triangle switch creates or deletes at least one tri
angle. Triangle switches can be used to define Markov chains which generate graphs with a given degree sequence and with many more triangles (3-cycles) than is typical in a uniformly random graph with the same degrees. We show that the set of triangle switches connects the set of all $d$-regular graphs on $n$ vertices, for all $dgeq 3$. Hence, any Markov chain which assigns positive probability to all triangle switches is irreducible on these graphs. We also investigate this question for 2-regular graphs.
The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle-free graphs with a
given rank and characterize all such graphs achieving the maximum order.
Given a graph $G=(V,E)$ whose vertices have been properly coloured, we say that a path in $G$ is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy-Vitaver Theorem that every properly coloured graph con
tains a colourful path on $chi(G)$ vertices. We explore a conjecture that states that every properly coloured triangle-free graph $G$ contains an induced colourful path on $chi(G)$ vertices and prove its correctness when the girth of $G$ is at least $chi(G)$. Recent work on this conjecture by Gyarfas and Sarkozy, and Scott and Seymour has shown the existence of a function $f$ such that if $chi(G)geq f(k)$, then an induced colourful path on $k$ vertices is guaranteed to exist in any properly coloured triangle-free graph $G$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
