Weakly toll convexity and proper interval graphs
A walk $u_0u_1 \ldots u_{k-1}u_k$ is a \textit{weakly toll walk} if $u_0u_i \in E(G)$ implies $u_i = u_1$ and $u_ju_k\in E(G)$ implies $u_j=u_{k-1}$. A set $S$ of vertices of $G$ is {\it weakly toll convex} if for any two non-adjacent vertices $x,y \in S$ any vertex in a weakly toll walk between $x$...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2024-04-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/9837/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850056391513866240 |
|---|---|
| author | Mitre C. Dourado Marisa Gutierrez Fábio Protti Silvia Tondato |
| author_facet | Mitre C. Dourado Marisa Gutierrez Fábio Protti Silvia Tondato |
| author_sort | Mitre C. Dourado |
| collection | DOAJ |
| description | A walk $u_0u_1 \ldots u_{k-1}u_k$ is a \textit{weakly toll walk} if $u_0u_i \in E(G)$ implies $u_i = u_1$ and $u_ju_k\in E(G)$ implies $u_j=u_{k-1}$. A set $S$ of vertices of $G$ is {\it weakly toll convex} if for any two non-adjacent vertices $x,y \in S$ any vertex in a weakly toll walk between $x$ and $y$ is also in $S$. The {\em weakly toll convexity} is the graph convexity space defined over weakly toll convex sets. Many studies are devoted to determine if a graph equipped with a convexity space is a {\em convex geometry}. An \emph{extreme vertex} is an element $x$ of a convex set $S$ such that the set $S\backslash\{x\}$ is also convex. A graph convexity space is said to be a convex geometry if it satisfies the Minkowski-Krein-Milman property, which states that every convex set is the convex hull of its extreme vertices. It is known that chordal, Ptolemaic, weakly polarizable, and interval graphs can be characterized as convex geometries with respect to the monophonic, geodesic, $m^3$, and toll convexities, respectively. Other important classes of graphs can also be characterized in this way. In this paper, we prove that a graph is a convex geometry with respect to the weakly toll convexity if and only if it is a proper interval graph. Furthermore, some well-known graph invariants are studied with respect to the weakly toll convexity. |
| format | Article |
| id | doaj-art-da2fd862867d4c6f98f020ec82c633bb |
| institution | DOAJ |
| issn | 1365-8050 |
| language | English |
| publishDate | 2024-04-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-da2fd862867d4c6f98f020ec82c633bb2025-08-20T02:51:42ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502024-04-01vol. 26:2Graph Theory10.46298/dmtcs.98379837Weakly toll convexity and proper interval graphsMitre C. DouradoMarisa GutierrezFábio Prottihttps://orcid.org/0000-0001-9924-0079Silvia TondatoA walk $u_0u_1 \ldots u_{k-1}u_k$ is a \textit{weakly toll walk} if $u_0u_i \in E(G)$ implies $u_i = u_1$ and $u_ju_k\in E(G)$ implies $u_j=u_{k-1}$. A set $S$ of vertices of $G$ is {\it weakly toll convex} if for any two non-adjacent vertices $x,y \in S$ any vertex in a weakly toll walk between $x$ and $y$ is also in $S$. The {\em weakly toll convexity} is the graph convexity space defined over weakly toll convex sets. Many studies are devoted to determine if a graph equipped with a convexity space is a {\em convex geometry}. An \emph{extreme vertex} is an element $x$ of a convex set $S$ such that the set $S\backslash\{x\}$ is also convex. A graph convexity space is said to be a convex geometry if it satisfies the Minkowski-Krein-Milman property, which states that every convex set is the convex hull of its extreme vertices. It is known that chordal, Ptolemaic, weakly polarizable, and interval graphs can be characterized as convex geometries with respect to the monophonic, geodesic, $m^3$, and toll convexities, respectively. Other important classes of graphs can also be characterized in this way. In this paper, we prove that a graph is a convex geometry with respect to the weakly toll convexity if and only if it is a proper interval graph. Furthermore, some well-known graph invariants are studied with respect to the weakly toll convexity.http://dmtcs.episciences.org/9837/pdfmathematics - combinatoricscomputer science - discrete mathematics05c75 |
| spellingShingle | Mitre C. Dourado Marisa Gutierrez Fábio Protti Silvia Tondato Weakly toll convexity and proper interval graphs Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - discrete mathematics 05c75 |
| title | Weakly toll convexity and proper interval graphs |
| title_full | Weakly toll convexity and proper interval graphs |
| title_fullStr | Weakly toll convexity and proper interval graphs |
| title_full_unstemmed | Weakly toll convexity and proper interval graphs |
| title_short | Weakly toll convexity and proper interval graphs |
| title_sort | weakly toll convexity and proper interval graphs |
| topic | mathematics - combinatorics computer science - discrete mathematics 05c75 |
| url | http://dmtcs.episciences.org/9837/pdf |
| work_keys_str_mv | AT mitrecdourado weaklytollconvexityandproperintervalgraphs AT marisagutierrez weaklytollconvexityandproperintervalgraphs AT fabioprotti weaklytollconvexityandproperintervalgraphs AT silviatondato weaklytollconvexityandproperintervalgraphs |