Computing the hull and interval numbers in the weakly toll convexity

DOI10.1016/J.TCS.2024.114501arXiv2303.07414MaRDI QIDQ6131192FDOQ6131192

M. Gutierrez, Mitre C. Dourado, Silvia B. Tondato, Fábio Protti

Publication date: 4 April 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A walk $u_0{u}_{1}ldots{u}_{k-1}{u}_k$ of a graph $G$ is a extit{weakly toll walk} if $u_0{u}_{k}otinE(G)$, $u_0{u}_{i}inE(G)$ implies $u_i=u_1$, and $u_j{u}_{k}inE(G)$ implies $u_j=u_{k-1}$. The {em weakly toll interval} of a set $SsubseteqV(G)$, denoted by $I(S)$, is formed by $S$ and the vertices belonging to some weakly toll walk between two vertices of $S$. Set $S$ is {it weakly toll convex} if $I(S)=S$. The {em weakly toll convex hull} of $S$, denote by $H(S)$, is the minimum weakly toll convex set containing $S$. The {em weakly toll interval number} of $G$ is the minimum cardinality of a set $SsubseteqV(G)$ such that $I(S)=V(G)$; and the {em weakly toll hull number} of $G$ is the minimum cardinality of a set $SsubseteqV(G)$ such that $H(S)=V(G)$. In this work, we show how to compute the weakly toll interval and the weakly toll hull numbers of a graph in polynomial time. In contrast, we show that determining the weakly toll convexity number of a graph $G$ (the size of a maximum weakly toll convex set distinct from $V(G)$) is NP-hard.

Full work available at URL: https://arxiv.org/abs/2303.07414

zbMATH Keywords

convex hullconvexityproper interval graphconvex geometryweakly toll walk

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Convexity in Graphs and Hypergraphs
• Convexity in partial cubes: the hull number
• On the computation of the hull number of a graph
• Convex sets in graphs. II: Minimal path convexity
• Convexities related to path properties on graphs
• Optimal decomposition by clique separators
• Geodesic Convexity in Graphs
• Some remarks on the geodetic number of a graph
• Complexity results related to monophonic convexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• The hull number of a graph
• On the hull number of some graph classes
• Convexity and HHD-Free Graphs
• The geodetic number of a graph
• Toll convexity
• On the geodetic number and related metric sets in Cartesian product graphs
• The geodetic number of the lexicographic product of graphs
• Weak bipolarizable graphs
• Geodetic Sets in Graphs
• Title not available (Why is that?)
• Computing the hull number in toll convexity
• On the toll number of a graph

Cited In (1)

• Characterizations of graph classes via convex geometries: a survey

This page was built for publication: Computing the hull and interval numbers in the weakly toll convexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131192)