Toll convexity
A walk W between two non-adjacent vertices in a graph G is called tolled if the first vertex of W is among vertices from W adjacent only to the second vertex of W, and the last vertex of W is among vertices from W adjacent only to the second-last vertex of W. In the resulting interval convexity, a s...
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2015
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/85849 |
| Aporte de: |
| id |
I19-R120-10915-85849 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Ciencias Exactas Matemática Graph in graph theory Vertex of a graph Detour monophonic |
| spellingShingle |
Ciencias Exactas Matemática Graph in graph theory Vertex of a graph Detour monophonic Alcón, Liliana Graciela Brešar, Boštjan Gologranc, Tanja Gutiérrez, Marisa Šumenjak, Tadeja Kraner Peterin, Iztok Tepeh, Aleksandra Toll convexity |
| topic_facet |
Ciencias Exactas Matemática Graph in graph theory Vertex of a graph Detour monophonic |
| description |
A walk W between two non-adjacent vertices in a graph G is called tolled if the first vertex of W is among vertices from W adjacent only to the second vertex of W, and the last vertex of W is among vertices from W adjacent only to the second-last vertex of W. In the resulting interval convexity, a set S ⊂ V(G) is toll convex if for any two non-adjacent vertices x, y ∈ S any vertex in a tolled walk between x and y is also in S. The main result of the paper is that a graph is a convex geometry (i.e. satisfies the Minkowski-Krein-Milman property stating that any convex subset is the convex hull of its extreme vertices) with respect to toll convexity if and only if it is an interval graph. Furthermore, some well-known types of invariants are studied with respect to toll convexity, and toll convex sets in three standard graph products are completely described. |
| format |
Articulo Articulo |
| author |
Alcón, Liliana Graciela Brešar, Boštjan Gologranc, Tanja Gutiérrez, Marisa Šumenjak, Tadeja Kraner Peterin, Iztok Tepeh, Aleksandra |
| author_facet |
Alcón, Liliana Graciela Brešar, Boštjan Gologranc, Tanja Gutiérrez, Marisa Šumenjak, Tadeja Kraner Peterin, Iztok Tepeh, Aleksandra |
| author_sort |
Alcón, Liliana Graciela |
| title |
Toll convexity |
| title_short |
Toll convexity |
| title_full |
Toll convexity |
| title_fullStr |
Toll convexity |
| title_full_unstemmed |
Toll convexity |
| title_sort |
toll convexity |
| publishDate |
2015 |
| url |
http://sedici.unlp.edu.ar/handle/10915/85849 |
| work_keys_str_mv |
AT alconlilianagraciela tollconvexity AT bresarbostjan tollconvexity AT gologranctanja tollconvexity AT gutierrezmarisa tollconvexity AT sumenjaktadejakraner tollconvexity AT peteriniztok tollconvexity AT tepehaleksandra tollconvexity |
| bdutipo_str |
Repositorios |
| _version_ |
1764820489001238531 |