On the Carathéodory number of interval and graph convexities

DOI10.1016/j.tcs.2013.09.004zbMath1419.05143OpenAlexW2046841024MaRDI QIDQ392186

Mitre C. Dourado, Dieter Rautenbach, Vinícius Fernandes dos Santos, Philipp Matthias Schäfer, Jayme Luiz Szwarcfiter

Publication date: 13 January 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.09.004

zbMATH Keywords

Carathéodory numbergeodetic convexity\(P_3\)-convexityconvexity spaceinterval convexitymonophonic convexity

Mathematics Subject Classification ID

Other problems of combinatorial convexity (52A37) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

\(P_3\)-hull number of graphs with diameter two ⋮ On the \(P_3\)-hull number of some products of graphs ⋮ Geodetic Convexity Parameters for Graphs with Few Short Induced Paths ⋮ \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers ⋮ Domination and convexity problems in the target set selection model ⋮ Efficient realizations of closure systems ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ Inapproximability results for graph convexity parameters ⋮ Geodetic convexity parameters for \((q, q - 4)\)-graphs ⋮ On the Carathéodory and exchange numbers of geodetic convexity in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On finite convexity spaces induced by sets of paths in graphs
• Irreversible conversion of graphs
• On geodetic sets formed by boundary vertices
• Complexity results related to monophonic convexity
• Triangle path transit functions, betweenness and pseudo-modular graphs
• The hull number of a graph
• On local convexity in graphs
• Convex sets in graphs. II: Minimal path convexity
• Convexity in graphs
• On triangle path convexity in graphs
• Convexities related to path properties on graphs
• On two-path convexity in multipartite tournaments
• Embedding tournaments in simple tournaments
• Some remarks on simple tournaments
• The All-Paths Transit Function of a Graph
• On the Hull Number of Triangle-Free Graphs
• Convexity in Graphs and Hypergraphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Convexity and HHD-Free Graphs
• On the Carathéodory Number for the Convexity of Paths of Order Three
• Some Elementary Properties of Interval Convexities