Buscar
Mostrando ítems 1-10 de 15
On nested and 2-nested graphs: Two subclasses of graphs between threshold and split graphs
(Sociedade Brasileira de Matematica, 2019-06)
A (0, 1)-matrix has the Consecutive Ones Property (C1P) for the rows if there is a permutation of its columns such that the ones in each row appear consecutively. We say a (0, 1)-matrix is nested if it has the consecutive ...
Normal Helly circular-arc graphs and its subclasses
(Elsevier Science, 2013-05)
A Helly circular-arc model M=(C,A) is a circle C together with a Helly family A of arcs of C. If no arc is contained in any other, then M is a proper Helly circular-arc model, if every arc has the same length, then M is a ...
The number of s-separated k-sets in various circles
(Combinatorial Mathematics Society of Australasia, 2021-02)
This article studies the number of ways of selecting k objects arranged in p circles of sizes n0,...,np−1 such that no two selected ones have less than s objects between them. If ni ≥ sk + 1 for all 0 ≤ i ≤ p − 1, this ...
The clique operator on circular-arc graphs
(Elsevier Science, 2010-06)
A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is ...
On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
(Elsevier Science, 2018-01)
Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edge intersection graph of paths on a grid (EPG graph), i.e., one can associate with each vertex of the graph a nontrivial path on a ...
Essential obstacles to Helly circular-arc graphs
(Elsevier Science, 2022-10-30)
A Helly circular-arc graph is the intersection graph of a set of arcs on a circle having the Helly property. We introduce essential obstacles, which are a refinement of the notion of obstacles, and prove that essential ...
Linear-time recognition of Helly circular-arc models and graphs
(Springer, 2011-02)
A circular-arc model M is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then · is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) ...
Partial characterizations of circle graphsDISCRETE APPLIED MATHEMATICSDISCRETE APPL MATH
(NORTH HOLLAND, 2011)
Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory
(Brown University, 2017-04)
This is the first of two chapters of a work in which we consider the unrestricted, minimal, and bounded representation problems for unit interval (UIG) and unit circular-arc (UCA) graphs. In the unrestricted version, a ...