Balancedness of some subclasses of circular-arc graphs
A graph is balanced if its clique-vertex incidence matrix is balanced, i.e., it does not contain a square submatrix of odd order with exactly two ones per row and per column. Interval graphs, obtained as intersection graphs of intervals of a line, are well-known examples of balanced graphs. A circul...
Guardado en:
| Autores principales: | , , |
|---|---|
| Publicado: |
2010
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v36_nC_p1121_Bonomo http://hdl.handle.net/20.500.12110/paper_15710653_v36_nC_p1121_Bonomo |
| Aporte de: |
| Sumario: | A graph is balanced if its clique-vertex incidence matrix is balanced, i.e., it does not contain a square submatrix of odd order with exactly two ones per row and per column. Interval graphs, obtained as intersection graphs of intervals of a line, are well-known examples of balanced graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. Circular-arc graphs generalize interval graphs, but are not balanced in general. In this work we characterize balanced graphs by minimal forbidden induced subgraphs restricted to graphs that belong to some classes of circular-arc graphs. © 2010 Elsevier B.V. |
|---|