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

Recognizing and testing isomorphism of Cayley graphs over an abelian group of order $4p$ in polynomial time

102   0   0.0 ( 0 )
 نشر من قبل Ilia Ponomarenko
 تاريخ النشر 2017
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




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

We construct a polynomial-time algorithm that given a graph $X$ with $4p$ vertices ($p$ is prime), finds (if any) a Cayley representation of $X$ over the group $C_2times C_2times C_p$. This result, together with the known similar result for circulant graphs, shows that recognising and testing isomorphism of Cayley graphs over an abelian group of order $4p$ can be done in polynomial time.



قيم البحث

اقرأ أيضاً

A Cayley graph over a group G is said to be central if its connection set is a normal subset of G. It is proved that for any two central Cayley graphs over explicitly given almost simple groups of order n, the set of all isomorphisms from the first graph onto the second can be found in time poly(n).
Let ${frak K}$ be a class of combinatorial objects invariant with respect to a given regular cyclic group. It is proved that the isomorphism of any two objects $X,Yin{frak K}$ can be tested in polynomial time in sizes of $X$ and $Y$.
We show that any connected Cayley graph $Gamma$ on an Abelian group of order $2n$ and degree $tilde{Omega}(log n)$ has at most $2^{n+1}(1 + o(1))$ independent sets. This bound is tight up to to the $o(1)$ term when $Gamma$ is bipartite. Our proof is based on Sapozhenkos graph container method and uses the Pl{u}nnecke-Rusza-Petridis inequality from additive combinatorics.
A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is proved that the isomorphism of circular-arc graphs can be tested by the Weisfeiler-Leman algorithm after individualization of two vertices.
75 - Dave Witte Morris 2020
Let $X$ be a connected Cayley graph on an abelian group of odd order, such that no two distinct vertices of $X$ have exactly the same neighbours. We show that the direct product $X times K_2$ (also called the canonical double cover of $X$) has only t he obvious automorphisms (namely, the ones that come from automorphisms of its factors $X$ and $K_2$). This means that $X$ is stable. The proof is short and elementary. The theory of direct products implies that $K_2$ can be replaced with members of a much more general family of connected graphs.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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