Convexity in Graphs and Hypergraphs

DOI10.1137/0607049zbMath0591.05056OpenAlexW1996471450WikidataQ56387984 ScholiaQ56387984MaRDI QIDQ3718757

Publication date: 1986

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0607049

zbMATH Keywords

convexity hypergraphs chordal graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (05C99)

Related Items

The contour of a bridged graph is geodetic, On geodetic sets formed by boundary vertices, Complexity aspects of the triangle path convexity, On the geodetic iteration number of the contour of a graph, Computational processes that appear to model human memory, A necessary condition for the equality of the clique number and the convexity number of a graph, Tree spanners on chordal graphs: complexity and algorithms, The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree, The recognition of geodetically connected graphs, Generating and enumerating digitally convex sets of trees, On local convexity in graphs, Induced path transit function, monotone and Peano axioms, On the \(P_3\)-hull number of some products of graphs, The structure of the centroid in a Ptolemaic graph, \(r\)-dominating cliques in graphs with hypertree structure, Bridged graphs and geodesic convexity, A general framework for path convexities, On bridged graphs and cop-win graphs, LexBFS-orderings and powers of chordal graphs, Computing the hull number in toll convexity, Reconstructing trees from digitally convex sets, Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs, A note on the convexity number of the complementary prisms of trees, The center and the distance center of a Ptolemaic graph, On diameters and radii of bridged graphs, Algorithmic and structural aspects of the \(P_3\)-Radon number, On the toll number of a graph, Closure lattices, Perfect elimination orderings for symmetric matrices, Inapproximability results and bounds for the Helly and Radon numbers of a graph, Matroids on convex geometries (cg-matroids), On the convexity number of graphs, On the Carathéodory number of interval and graph convexities, On the \(P_3\)-hull number of Hamming graphs, The maximum time of 2-neighbor bootstrap percolation: complexity results, On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent, Equivalence between hypergraph convexities, The maximum infection time in the geodesic and monophonic convexities, Steiner distance and convexity in graphs, Characterization and recognition of Radon-independent sets in split graphs, Excluded-minor characterizations of antimatroids arisen from posets and graph searches., Computing simple-path convex hulls in hypergraphs, On the geodetic and the hull numbers in strong product graphs, The pre-hull number and lexicographic product, Decomposable convexities in graphs and hypergraphs, An upper bound on the \(P_3\)-Radon number, Toll number of the strong product of graphs, On the contour of graphs, The Carathéodory number of the \(P_3\) convexity of chordal graphs, On the geodeticity of the contour of a graph, Some properties of graph centroids, Graphs with a minimal number of convex sets, Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs, Peakless functions on graphs, A convex polytope and an antimatroid for any given, finite group, On the contour of bipartite graphs, Helly theorems for 3-Steiner and 3-monophonic convexity in graphs, Geodeticity of the contour of chordal graphs, Toll convexity, The induced path function, monotonicity and betweenness, Absolute retracts and varieties generated by chordal graphs, Closure spaces that are not uniquely generated, An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time, Fast minimal triangulation algorithm using minimum degree criterion, Toll number of the Cartesian and the lexicographic product of graphs, Convexities related to path properties on graphs, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Separation properties of 3-Steiner and 3-monophonic convexity in graphs, On the parameterized complexity of the geodesic hull number, On the Steiner, geodetic and hull numbers of graphs, Partitioning a graph into convex sets, Complexity results related to monophonic convexity, Characterizations of convex spaces and anti-matroids via derived operators, Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs, Geodetic convexity parameters for \((q, q - 4)\)-graphs, Characterizations of \(L\)-convex spaces via domain theory, Decomposability of abstract and path-induced convexities in hypergraphs, Special eccentric vertices for the class of chordal graphs and related classes, Perfect elimination orderings of chordal powers of graphs, Local Steiner convexity, On the geodesic pre-hull number of a graph, Triangle path transit functions, betweenness and pseudo-modular graphs, Lattice-equivalence of convex spaces, Avoidable vertices and edges in graphs: existence, characterization, and applications, Convex and quasiconvex functions in metric graphs, Consequences of an algorithm for bridged graphs, Canonical and monophonic convexities in hypergraphs, On the computation of the hull number of a graph, On 3-Steiner simplicial orderings, Oracles for vertex elimination orderings, Rebuilding convex sets in graphs, Convex geometries over induced paths with bounded length, Diameter estimates for graph associahedra, On the spectrum and number of convex sets in graphs, Clique graphs and Helly graphs, The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects, A characterization of totally balanced hypergraphs, Closure systems and their structure, Enumerating maximal consistent closed sets in closure systems, An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs, On the geodetic hull number of \(P_{k}\)-free graphs, Geodetic Convexity Parameters for Graphs with Few Short Induced Paths, Two classes of graphs in which some problems related to convexity are efficiently solvable, Unnamed Item, Resolutions of convex geometries, The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results, A new notion of convexity in digraphs with an application to Bayesian networks, Algorithms and complexity for geodetic sets on partial grids, On the hull number on cycle convexity of graphs, A unifying view on recombination spaces and abstract convex evolutionary search, Convex Partitions of Graphs, Algorithmic Aspects of Monophonic Convexity, A story of diameter, radius, and (almost) Helly property, Maximal closed set and half-space separations in finite closure systems, Bounds and algorithms for geodetic hulls, Target set selection with maximum activation time, Partition coefficients of acyclic graphs, Computing the hull and interval numbers in the weakly toll convexity, On the monophonic convexity in complementary prisms, Probe Ptolemaic Graphs, Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements, Domination and convexity problems in the target set selection model, Monophonic convexity in weighted graphs, Antimatroids, Betweenness, Convexity, Unnamed Item, CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT, The All-Paths Transit Function of a Graph, Transformations of Concept Graphs:, Unnamed Item, Unnamed Item, Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs, The hull number of powers of cycle graphs under restricted conditions, Computational and structural aspects of the geodetic and the hull numbers of shadow graphs, Computational and structural aspects of the geodetic and the hull numbers of shadow graphs, Minimum Eccentricity Shortest Paths in Some Structured Graph Classes, On the Convexity of Paths of Length Two in Undirected Graphs, Finding a Maximum-Weight Convex Set in a Chordal Graph, THE HULL NUMBER OF POWERS OF CYCLES, Some structural, metric and convex properties on the boundary of a graph

Cites Work