CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT

DOI10.1142/S1793830912500632zbMath1257.05106OpenAlexW2036136115MaRDI QIDQ4903647

Mauro Mezzini, Marina Moscarini, Francesco Mario Malvestuto

Publication date: 24 January 2013

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830912500632

zbMATH Keywords

geodesic convexitymonophonic convexityPtolemaic graphsminimal vertex separators\(\gamma\)-acyclic hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Related Items

A necessary condition for the equality of the clique number and the convexity number of a graph, Two classes of graphs in which some problems related to convexity are efficiently solvable, On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent, On the geodeticity of the contour of a graph, Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs

Cites Work

• Equivalence between hypergraph convexities
• Canonical and monophonic convexities in hypergraphs
• On the computation of the hull number of a graph
• Decomposition by clique separators
• Bridged graphs and geodesic convexity
• On hypergraph acyclicity and graph chordality
• Convex sets in graphs. II: Minimal path convexity
• Minimal vertex separators of chordal graphs
• The geodetic number of a graph
• Treewidth. Computations and approximations
• An implementation of the iterative proportional fitting procedure by propagation trees.
• Computing simple-path convex hulls in hypergraphs
• Optimal decomposition by clique separators
• The All-Paths Transit Function of a Graph
• On the Desirability of Acyclic Database Schemes
• Degrees of acyclicity for hypergraphs and relational database schemes
• Convexity in Graphs and Hypergraphs
• A characterization of ptolemaic graphs