اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn maximal dominating forest and four colors theorem of planar graph
82
0
0.0
(
0
)
تأليف
Li Xi
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For a given graph $G(V,E)$ and one of its dominating set $S$, the subgraph $Gleft[Sright]$ induced by $S$ is a called a dominating tree if $Gleft[Sright]$ is a tree. Not all graphs has a dominating tree, we will show that a graph without cut vertices has at least one dominating tree. Analogously, if $Gleft[Sright]$ is a forest, then it is called a dominating forest. As special structures of graphs, dominating tree and dominating forest have many interesting application, and we will focus on its application on the problem of planar graph coloring.
قيم البحث
اقرأ أيضاً
For the four-color theorem that has been developed over one and half centuries, all people believe it right but without complete proof convincing all1-3. Former proofs are to find the basic four-colorable patterns on a planar graph to reduce a map co
loring4-6, but the unavoidable set is almost limitless and required recoloring hardly implements by hand7-14. Another idea belongs to formal proof limited to logical operation15. However, recoloring or formal proof way may block people from discovering the inherent essence of a coloring graph. Defining creation and annihilation operations, we show that four colors are sufficient to color a map and how to color it. We find what trapped vertices and boundary-vertices are, and how they decide how many colors to be required in coloring arbitrary maps. We reveal that there is the fourth color for new adding vertex differing from any three coloring vertices in creation operation. To implement a coloring map, we also demonstrate how to color an arbitrary map by iteratively using creation and annihilation operations. We hope our hand proof is beneficial to understand the mechanisms of the four-color theorem.
We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a $(7-epsilon)$-approximation of a minimum dominating set on planar graphs, for any positive constant $epsilon$. In prior work, the best low
er bound on the approximation ratio has been $5-epsilon$; there is also an upper bound of $52$.
Even though flt is a number theoretic result we prove that the result depends on the topological as well as the field structure of the underlying space.
The purpose of these notes is to present a fairly complete proof of the classification Theorem for compact surfaces. Other presentations are often quite informal (see the references in Chapter V) and we have tried to be more rigorous. Our main source
of inspiration is the beautiful book on Riemann Surfaces by Ahlfors and Sario. However, Ahlfors and Sarios presentation is very formal and quite compact. As a result, uninitiated readers will probably have a hard time reading this book. Our goal is to help the reader reach the top of the mountain and help him not to get lost or discouraged too early. This is not an easy task! We provide quite a bit of topological background material and the basic facts of algebraic topology needed for understanding how the proof goes, with more than an impressionistic feeling. We hope that these notes will be helpful to readers interested in geometry, and who still believe in the rewards of serious hiking!
We study the rank N magnificent four theory, which is the supersymmetric localization of U(N) super-Yang-Mills theory with matter (a super-group U(N|N) gauge theory) on a Calabi-Yau fourfold. Our theory contains the higher rank Donaldson-Thomas theor
y of threefolds. We conjecture an explicit formula for the partition function Z, and report on the performed checks. The partition function Z has a free field representation. Surprisingly, it depends on the Coulomb and mass parameters in a simple way. We also clarify the definition of the instanton measure.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
