ترغب بنشر مسار تعليمي؟ اضغط هنا

Universal Rigidity of Complete Bipartite Graphs

195   0   0.0 ( 0 )
 نشر من قبل Steven Gortler
 تاريخ النشر 2015
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

We describe a very simple condition that is necessary for the universal rigidity of a complete bipartite framework $(K(n,m),p,q)$. This condition is also sufficient for universal rigidity under a variety of weak assumptions, such as general position. Even without any of these assumptions, in complete generality, we extend these ideas to obtain an efficient algorithm, based on a sequence of linear programs, that determines whether an input framework of a complete bipartite graph is universally rigid or not.



قيم البحث

اقرأ أيضاً

This note gives a detailed proof of the following statement. Let $din mathbb{N}$ and $m,n ge d + 1$, with $m + n ge binom{d+2}{2} + 1$. Then the complete bipartite graph $K_{m,n}$ is generically globally rigid in dimension $d$.
Let $mathrm{rex}(n, F)$ denote the maximum number of edges in an $n$-vertex graph that is regular and does not contain $F$ as a subgraph. We give lower bounds on $mathrm{rex}(n, F)$, that are best possible up to a constant factor, when $F$ is one of $C_4$, $K_{2,t}$, $K_{3,3}$ or $K_{s,t}$ when $t>s!$.
The symmetries of complex molecular structures can be modeled by the {em topological symmetry group} of the underlying embedded graph. It is therefore important to understand which topological symmetry groups can be realized by particular abstract gr aphs. This question has been answered for complete graphs; it is natural next to consider complete bipartite graphs. In previous work we classified the complete bipartite graphs that can realize topological symmetry groups isomorphic to $A_4$, $S_4$ or $A_5$; in this paper we determine which complete bipartite graphs have an embedding in $S^3$ whose topological symmetry group is isomorphic to $mathbb{Z}_m$, $D_m$, $mathbb{Z}_r times mathbb{Z}_s$ or $(mathbb{Z}_r times mathbb{Z}_s) ltimes mathbb{Z}_2$.
Total dominator total coloring of a graph is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. The minimum namber of the color classes of a total dominator total coloring of a graph is called the total dominator total chromatic number of the graph. Here, we will find the total dominator chromatic numbers of wheels, complete bipartite graphs and complete graphs.
We prove that universal second-order rigidity implies universal prestress stability and that triangulated convex polytopes in three-space (with holes appropriately positioned) are prestress stable.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا