Computing the hull number in toll convexity

DOI10.1007/S10479-022-04694-4zbMATH Open1492.05146arXiv1905.00109OpenAlexW2942955486MaRDI QIDQ2159554FDOQ2159554

Authors: Mitre C. Dourado 

Publication date: 1 August 2022

Published in: Annals of Operations Research (Search for Journal in Brave)

Abstract: A walk $W$ between vertices $u$ and $v$ of a graph $G$ is called a {em tolled walk between $u$ and $v$} if $u$, as well as $v$, has exactly one neighbour in $W$. A set $SsubseteqV(G)$ is {em toll convex} if the vertices contained in any tolled walk between two vertices of $S$ are contained in $S$. The {em toll convex hull of $S$} is the minimum toll convex set containing~$S$. The {em toll hull number of $G$} is the minimum cardinality of a set $S$ such that the toll convex hull of $S$ is $V(G)$. The main contribution of this work is an algorithm for computing the toll hull number of a general graph in polynomial time.

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

Recommendations

• Toll convexity
• On the toll number of a graph
• Toll number of the strong product of graphs
• Toll number of the Cartesian and the lexicographic product of graphs
• Forcing subsets for some types of convex sets in a graph

zbMATH Keywords

hull numbertoll convexityextreme vertexminimum toll hull sets

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Title not available (Why is that?)
• Convexity in Graphs and Hypergraphs
• The theory of convex geometries
• 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
• Open packing, total domination, and the \(P_3\)-Radon number
• Optimal decomposition by clique separators
• Geodesic Convexity in Graphs
• An upper bound on the \(P_3\)-Radon number
• Irreversible conversion of graphs
• Complexity results related to monophonic convexity
• On the hull number of some graph classes
• Hull number: \(P_5\)-free graphs and reduction rules
• Toll convexity
• Toll number of the Cartesian and the lexicographic product of graphs
• Inapproximability results for graph convexity parameters
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• Some remarks on the convexity number of a graph
• The Geodetic Hull Number is Hard for Chordal Graphs

Cited In (4)

• On the toll number of a graph
• Characterizations of graph classes via convex geometries: a survey
• Computing the hull and interval numbers in the weakly toll convexity
• Axiomatic characterization of the toll walk function of some graph classes

This page was built for publication: Computing the hull number in toll convexity

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