Artículo
Convex geometries over induced paths with bounded length
Fecha de publicación:
01/2023
Editorial:
Elsevier Science
Revista:
Discrete Mathematics
ISSN:
0012-365X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
In this paper we introduce the notion of lk-convexity, a natural restriction of the monophonic convexity. Let G be a graph and k≥2 an integer. A subset S⊆V(G) is lk-convex if and only if for any pair of vertices x,y of S, each induced path of length at most k connecting x and y is completely contained in the subgraph induced by S. The lk-convexity consists of all lk-convex subsets of G. In this work, we characterize lk-convex geometries (graphs that are convex geometries with respect to the lk-convexity) for k∈{2,3}. We show that a graph G is an l2-convex geometry if and only if G is a chordal P4-free graph, and an l3-convex geometry if and only if G is a chordal graph with diameter at most three such that its induced gems satisfy a special “solving” property. As far as the authors know, the class of l3-convex geometries is the first example of a non-hereditary class of convex geometries.
Palabras clave:
CHORDAL GRAPH
,
CONVEX GEOMETRY
,
CONVEXITY
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Citación
Gutierrez, Marisa; Protti, Fabio; Tondato, Silvia Beatriz; Convex geometries over induced paths with bounded length; Elsevier Science; Discrete Mathematics; 346; 1; 1-2023; 1-9
Compartir
Altmétricas