Powers of Circular-Arc Models

FRANCISCO J. SOULIGNAC; PABLO TERLISKY

Rio de Janeiro

Workshop; VIII Latin American Workshop on Cliques in Graphs; 2018

Universidad Federal do Rio de Janeiro, CEFET/RJ, Universidad do Estado do Rio de Janeiro

A proper circular-arc (PCA) model is a pair M = (C, A) such that C is a circle and A is a finite family of inclusion-free arcs of C. Each arc A of A has two extremes: its beginning point s(A) and its ending point t(A), which are the first and last points of A reached when C is clockwise traversed, respectively. A PCA model is a (Circ,Len)-CA model when the circumference of the circle is Circ and all arcs of A have length Len. In general, M is a unit circular-arc (UCA) model when it is a (Circ,Len)-CA model for some Circ, Len. Two PCA models are equivalent if the extremes of their arcs appear in the same order when C is clockwise traversed.For any A in A, its next arc is defined as the arc Nxt(A)=A´ such that s(A´) is the last beginning point reached before t(A) when C is clockwise traversed. The k-th power of A is defined recursively as A^1=A and A^{k=(s(A), t(Nxt(A^{k-1))), while the k-th power of a model M is M^k = (C,{A^kmid Ain A). For a (Circ, Len)-CA model U, we define the j-th multiple of U as jcdotU = (C, {(s(A), s(A)+jLen)mid Ain A).In this work we study the question of whether some model M is k-multiplicative, i.e., determining if the models M^i and icdotM are equivalent for all i leq k. For k=1, this question is precisely the recognition problem for UCA models, which was first solved by Tucker. Soulignac and Terlisky recently proposed a new characterization of (Circ,Len)-CA models that yields a  simpler algorithm forthe recognition of UCA models, based on Pirlot´s synthetic graphs. In this work we generalize synthetic graphs to study the multiplicative problem. Our results can be applied to characterizewhich powers of UCA graphs are UCA graphs as well.