Extremal unit 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 unit circular-arc (UCA) model is a pair M = (C, A) such that C is a circle and A is a finite family of arcs of C, all having the same length. A UCA model M is called a (Circ,Len)-CA model when |C| = Circ and the length of the arcs of A is Len.  The model M is equivalent to a UCA model M´ when the extremes of M and M´ appear in the same order when their respective circles are clockwise traversed, whereas M and M´ are isomorphic when their intersection graphs are isomorphic.If Circ leq Circ´ and Len leq Len´ for every (Circ´,Len´)-CA model M´ equivalent (resp. isomorphic) to M, then M is said to be minimal (resp. minimum).  It is already known that every UCA model is equivalent (resp. isomorphic) to some minimal (resp. minimum) UCA model.  For n in N, each (Circ,Len)-CA model with maximum Circ (resp. Len) among those minimal models with n arcs are said to be circle extremal (resp. arc extremal).  Similarly, the (Circ, Len)-CA models with maximum Circ (resp. Len) among those minimum models with n arcs are called circle isoextremal (resp. arc isoextremal).  Finally, those models that are both circle and arc (iso)extremal simply are referred to as being (iso)extremal.Lin and Szwarcfiter (Unit Circular-Arc Graph Representations and Feasible Circulations, SIAM J. Disc. Math., 22(1), pp. 409--423) left open the problem of determining the value Circ (resp. Len) of circle (resp. arc) isoextremal models. In this work we solve these problems and their analogous problems for extremal models, while we characterize those (circle, arc) (iso)extremal models, for every n in N.