Computing the hull number in toll convexity

DOI10.1007/S10479-022-04694-4MaRDI QIDQ2159554zbMATH OpenOpenAlexFDO

Authors Mitre C. Dourado

Publication date 1 August 2022

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

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

zbMATH Keywords

hull numbertoll convexityextreme vertexminimum toll hull sets

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• An upper bound on the \(P_3\)-Radon number
• Complexity results related to monophonic convexity
• Convex sets in graphs. II: Minimal path convexity
• Convexity in Graphs and Hypergraphs
• Convexity in partial cubes: the hull number
• Geodesic Convexity in Graphs
• Hull number: \(P_5\)-free graphs and reduction rules
• Inapproximability results for graph convexity parameters
• Irreversible conversion of graphs
• On the computation of the hull number of a graph
• On the hull number of some graph classes
• Open packing, total domination, and the \(P_3\)-Radon number
• Optimal decomposition by clique separators
• 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
• The theory of convex geometries
• Toll convexity
• Toll number of the Cartesian and the lexicographic product of graphs

Cited in

(10)

• Forcing subsets for some types of convex sets in a graph
• Toll convexity
• Characterizations of graph classes via convex geometries: a survey
• 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
• Weakly toll convexity and proper interval graphs
• Toll path domination in graphs
• 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)