Premium
Graphs with intrinsic s 3 convexities
Author(s) -
Bandelt HansJürgen
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130208
Subject(s) - convexity , combinatorics , mathematics , regular polygon , path (computing) , convex set , graph , discrete mathematics , convex optimization , computer science , geometry , financial economics , economics , programming language
Separation properties for some intrinsic convexities of graphs are investigated. The most natural convexities defined on a graph are the induced path convexity and the geodesic convexity. A set A of vertices is convex with respect to the former convexity if A contains every induced path connecting two vertices of A . In particular, a characterization of those graphs is given in which all such convex sets are the intersections of halfspaces (i.e., convex sets with convex complements).