On the Convexity of Paths of Length Two in Undirected Graphs

DOI10.1016/j.endm.2009.02.003zbMath1267.05248OpenAlexW2039535864MaRDI QIDQ2839205

Mitre C. Dourado, Carmen C. Centeno, Jayme Luiz Szwarcfiter

Publication date: 4 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.02.003

zbMATH Keywords

polynomial time algorithmsconvexity numberhull numberconvex subset of a graphsmallest hull set

Mathematics Subject Classification ID

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

Related Items (9)

A general framework for path convexities ⋮ \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers ⋮ Complete characterizations of the 2-domination and \(\mathcal{P}_3\)-hull number polytopes ⋮ Domination and convexity problems in the target set selection model ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ Computing the \(\mathcal{P}_3\)-hull number of a graph, a polyhedral approach ⋮ Graphs with few \(P_4\)'s under the convexity of paths of order three ⋮ Inapproximability results for graph convexity parameters ⋮ On the complexity of the \(P_{3}\)-hull number of the Cartesian product of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dominating sets for split and bipartite graphs
• On the computation of the hull number of a graph
• The hull number of a graph
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Convex sets in graphs. II: Minimal path convexity
• Convexity in graphs
• On triangle path convexity in graphs
• Separation of two convex sets in convexity structures
• Some remarks on the convexity number of a graph
• Embedding tournaments in simple tournaments
• Some remarks on simple tournaments
• Algorithmic Aspects of Monophonic Convexity
• Convexity in Graphs and Hypergraphs
• Convexity and HHD-Free Graphs
• Computational Complexity of Geodetic Set
• Random disease on the square grid
• Convex independence and the structure of clone-free multipartite tournaments
• Convexity in oriented graphs

This page was built for publication: On the Convexity of Paths of Length Two in Undirected Graphs