On the convexity number of graphs

DOI10.1007/s00373-011-1049-7zbMath1256.05123OpenAlexW2028857914MaRDI QIDQ1926045

Dieter Rautenbach, Mitre C. Dourado, Fábio Protti, Jayme Luiz Szwarcfiter

Publication date: 27 December 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-011-1049-7

zbMATH Keywords

shortest pathconvex hullconvex setconvexity number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

Complexity aspects of the triangle path convexity ⋮ A necessary condition for the equality of the clique number and the convexity number of a graph ⋮ Geodetic Convexity Parameters for Graphs with Few Short Induced Paths ⋮ A note on the convexity number of the complementary prisms of trees ⋮ On finding convex cuts in general, bipartite and plane graphs ⋮ The strong convexity spectra of grids ⋮ Algorithmic Aspects of Monophonic Convexity ⋮ Convex \(p\)-partitions of bipartite graphs ⋮ \textsc{Minimum Surgical Probing} with convexity constraints ⋮ Domination and convexity problems in the target set selection model ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ Graphs with a minimal number of convex sets ⋮ Inapproximability results for graph convexity parameters ⋮ Geodetic convexity parameters for \((q, q - 4)\)-graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The theory of convex geometries
• Convexity in graphs
• Some remarks on the convexity number of a graph
• A lower bound for the convexity number of some graphs
• The convexity number of a graph
• Convex sets under some graph operations
• Rebuilding convex sets in graphs
• Convexity in Graphs and Hypergraphs
• Graph Classes: A Survey

This page was built for publication: On the convexity number of graphs