Convex sets in graphs. II: Minimal path convexity

DOI10.1016/0095-8956(88)90039-1zbMath0672.52001OpenAlexW2117475001WikidataQ56503424 ScholiaQ56503424MaRDI QIDQ1120125

Publication date: 1988

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(88)90039-1

zbMATH Keywords

Carathéodory number Helly number Radon number graph-convexity minimal path convexity spaces

Mathematics Subject Classification ID

Axiomatic and generalized convexity (52A01) Helly-type theorems and geometric transversal theory (52A35) Connectivity (05C40)

Related Items

Complexity aspects of the triangle path convexity, A necessary condition for the equality of the clique number and the convexity number of a graph, \(P_3\)-hull number of graphs with diameter two, The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree, On local convexity in graphs, Induced path transit function, monotone and Peano axioms, On the geodetic hull number of \(P_{k}\)-free graphs, On the \(P_3\)-hull number of some products of graphs, A Helly theorem for geodesic convexity in strongly dismantlable graphs, Geodetic Convexity Parameters for Graphs with Few Short Induced Paths, Complexity of determining the maximum infection time in the geodetic convexity, Two classes of graphs in which some problems related to convexity are efficiently solvable, Bridged graphs and geodesic convexity, A general framework for path convexities, Computing the hull number in toll convexity, On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products, Some Steiner concepts on lexicographic products of graphs, Algorithmic and structural aspects of the \(P_3\)-Radon number, On the toll number of a graph, \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers, A Radon theorem for Helly graphs, A Helly theorem in weakly modular space, Inapproximability results and bounds for the Helly and Radon numbers of a graph, Tverberg numbers for cellular bipartite graphs, Interval function, induced path function, (claw, paw)-free graphs and axiomatic characterizations, The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results, 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 monophonic rank of a graph, On the hull number on cycle convexity of graphs, On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent, Equivalence between hypergraph convexities, Target set selection with maximum activation time, A note on the interval function of a disconnected graph, Convex Independence in Permutation Graphs, The maximum infection time in the geodesic and monophonic convexities, On the geodetic iteration number of distance-hereditary graphs, Computing the hull and interval numbers in the weakly toll convexity, Segment transit function of the induced path function of graphs and its first-order definability, On the monophonic convexity in complementary prisms, On two-path convexity in multipartite tournaments, Characterization and recognition of Radon-independent sets in split graphs, Computing simple-path convex hulls in hypergraphs, Domination and convexity problems in the target set selection model, Strict betweennesses induced by posets as well as by graphs, Axiomatic characterization of the interval function of a bipartite graph, The pre-hull number and lexicographic product, Antimatroids, Betweenness, Convexity, Axiomatic Characterization of the Interval Function of a Bipartite Graph, Decomposable convexities in graphs and hypergraphs, An upper bound on the \(P_3\)-Radon number, On the contour of graphs, The Carathéodory number of the \(P_3\) convexity of chordal graphs, Convex sets in lexicographic products of graphs, On the geodeticity of the contour of a graph, Graphs with few \(P_4\)'s under the convexity of paths of order three, Inapproximability results related to monophonic convexity, CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT, On the complexity of the \(P_{3}\)-hull number of the Cartesian product of graphs, On finite convexity spaces induced by sets of paths in graphs, Toll convexity, The All-Paths Transit Function of a Graph, The induced path function, monotonicity and betweenness, Unnamed Item, Convexities related to path properties on graphs, On the parameterized complexity of the geodesic hull number, Complexity results related to monophonic convexity, Helly and exchange numbers of geodesic and Steiner convexities in lexicographic product of graphs, Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs, Geodetic convexity parameters for \((q, q - 4)\)-graphs, The induced path transit function and the Pasch axiom, On the Carathéodory and exchange numbers of geodetic convexity in graphs, Axiomatic Characterization of Claw and Paw-Free Graphs Using Graph Transit Functions, Decomposability of abstract and path-induced convexities in hypergraphs, On the \(P_3\)-hull number of Kneser graphs, Covering graphs with convex sets and partitioning graphs into convex sets, Triangle path transit functions, betweenness and pseudo-modular graphs, Selfishness of convex bodies and discrete point sets, On the Convexity of Paths of Length Two in Undirected Graphs, Complexity aspects of \(\ell\)-chord convexities, Canonical and monophonic convexities in hypergraphs, Intersecting sets in midset spaces. I, Convex geometries over induced paths with bounded length, The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects, Some structural, metric and convex properties on the boundary of a graph

Cites Work