A note on Helly-B1-EPG graphs | ||
| dc.conicet.organizacion | Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata | |
| dc.conicet.organizacion | Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata | |
| dc.conicet.organizacion | Universidade Federal do Rio de Janeiro | |
| dc.contributor.author | Alcón, Liliana Graciela | |
| dc.contributor.author | Mazzoleni, María Pía | |
| dc.contributor.author | Dias Dos Santos, Tanilson | |
| dc.date.issued | 2021-10 | |
| dc.description.abstract | Edge intersection graphs of paths on a grid (EPG graphs) aregraphs whose vertices can be represented as nontrivial paths on agrid such that two vertices are adjacent if and only if the corresponding paths share at least one edge of the grid. When the paths haveat most one change of direction (bend) these graphs are called B1-EPG graphs. In this paper, we delimit some subclasses of B1-EPGgraphs that admit a Helly-B1-EPG representation. It is known thatB1-EPG and Helly-B1-EPG are hereditary classes, so they can becharacterized by forbidden structures. In both cases, finding thewhole list of minimal forbidden induced subgraphs are challengingopen problems. Taking a step towards solving those problems, wedescribe a few structures at least one of which will necessarily bepresent in any B1-EPG graph that does not admit a Helly representation. In addition, we show that the well known families of Blockgraphs, Cactus and Line of Bipartite graphs are totally contained inthe class Helly-B1-EPG. | es |
| dc.description.fil | Fil: Alcón, Liliana Graciela. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata; Argentina | |
| dc.description.fil | Fil: Mazzoleni, María Pía. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata; Argentina | |
| dc.description.fil | Fil: Dias Dos Santos, Tanilson. Universidade Federal do Rio de Janeiro; Brasil | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Alcón, Liliana Graciela; Mazzoleni, María Pía; Dias Dos Santos, Tanilson; A note on Helly-B1-EPG graphs; Sociedad Brasilera de Matemàtica; Matemática Contemporânea; 48; 10-2021; 22-30 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0103-9059 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/160294 | |
| dc.journal.pagination | 22-30 | es |
| dc.journal.pais | Brasil | es |
| dc.journal.title | Matemática Contemporânea | es |
| dc.journal.volume | 48 | es |
| dc.language.iso | eng | es |
| dc.publisher | Sociedad Brasilera de Matemàtica | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.21711/231766362021/rmc483 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://mc.sbm.org.br/wp-content/uploads/sites/9/sites/9/2022/01/Article-03-vol-48.pdf | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | EDGE- INYTERSECTION GRAPHS OF PATHS ON A GRID | es |
| dc.subject | HELLY PROPERTY | es |
| dc.subject | SINGLE BEND PATHS | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | A note on Helly-B1-EPG graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.2fdc3528-ae88-46f6-af74-917a813292ce_A.pdf
- Tamaño:
- 381.99 KB
- Formato:
- Adobe Portable Document Format