2005-02-28
Convexities related to path properties on graphs
Publication
Publication
Discrete Mathematics , Volume 290 - Issue 2-3 p. 117- 131
A feasible family of paths in a connected graph G is a family that contains at least one path between any pair of vertices in G. Any feasible path family defines a convexity on G. Well-known instances are: the geodesics, the induced paths, and all paths. We propose a more general approach for such 'path properties'. We survey a number of results from this perspective, and present a number of new results. We focus on the behaviour of such convexities on the Cartesian product of graphs and on the classical convexity invariants, such as the Carathéodory, Helly and Radon numbers in relation with graph invariants, such as the clique number and other graph properties.
Additional Metadata | |
---|---|
, , , | |
doi.org/10.1016/j.disc.2003.07.014, hdl.handle.net/1765/74146 | |
Discrete Mathematics | |
Organisation | Erasmus School of Economics |
Changat, M., Mulder, M., & Sierksma, G. (2005). Convexities related to path properties on graphs. Discrete Mathematics, 290(2-3), 117–131. doi:10.1016/j.disc.2003.07.014 |