Intervals in matroid basis graphs |
| |
| Authors: | Stephen B Maurer |
| |
| Institution: | Mathematics Department, Princeton University, Princeton, N.J. 08540, USA |
| |
| Abstract: | An interval in a graph is a subgraph induced by all the vertices on shortest paths between two given vertices. Intervals in matroid basis graphs satisfy many nice properties. Key results are: (1) any two vertices of a basis graph are together in some longest interval; (2) every basis graph with the minimum number of vertices for its diameter is an interval, indeed a hypercube. (1) turns out to be a simple case of a theorem in Edmonds' theory of matroid partition. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
