On the convexity of paths of length two in undirected graphs

DOI10.1016/J.ENDM.2009.02.003MaRDI QIDQ2839205zbMATH OpenOpenAlexFDO

Authors C. C. Centeno, Mitre C. Dourado, Jayme L. 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

convex subset of a graphconvexity numberhull numberpolynomial time algorithmssmallest hull set

Mathematics Subject Classification ID

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

Recommendations

• The convexity of induced paths of order three and applications: complexity aspects
• On the computation of the hull number of a graph
• On the convexity number of graphs
• \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
• On the hull number of some graph classes

Cites work

• Algorithmic Aspects of Monophonic Convexity
• Computational Complexity of Geodetic Set
• Convex independence and the structure of clone-free multipartite tournaments
• Convex sets in graphs. II: Minimal path convexity
• Convexity and HHD-Free Graphs
• Convexity in graphs
• Convexity in Graphs and Hypergraphs
• Convexity in oriented graphs
• Dominating sets for split and bipartite graphs
• Embedding tournaments in simple tournaments
• scientific article; zbMATH DE number 6007730 (Why is no real title available?)
• scientific article; zbMATH DE number 5531985 (Why is no real title available?)
• scientific article; zbMATH DE number 3545692 (Why is no real title available?)
• scientific article; zbMATH DE number 5066400 (Why is no real title available?)
• On the computation of the hull number of a graph
• On triangle path convexity in graphs
• Random disease on the square grid
• Separation of two convex sets in convexity structures
• Some remarks on simple tournaments
• Some remarks on the convexity number of a graph
• The hull number of a graph
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs

Cited in

(14)

• Convex sets in graphs. II: Minimal path convexity
• On triangle path convexity in graphs
• 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
• \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
• Domination and convexity problems in the target set selection model
• On the length of simplex paths: The assignment case
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• Inapproximability results for graph convexity parameters
• Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs
• On the complexity of the \(P_{3}\)-hull number of the Cartesian product of graphs
• Complete characterizations of the 2-domination and \(\mathcal{P}_3\)-hull number polytopes
• The iteration time and the general position number in graph convexities
• On the hull and interval numbers of oriented graphs

This page was built for publication: On the convexity of paths of length two in undirected graphs

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