Note on the gammoids arising from undirected graphs (Q1813281)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Note on the gammoids arising from undirected graphs |
scientific article |
Statements
Note on the gammoids arising from undirected graphs (English)
0 references
25 June 1992
0 references
We consider strict gammoids, which arise from undirected graphs. We exhibit a minimal example of a strict gammoid, which cannot arise in this way and we interpret the Ingleton and Piff's characterization of the strict grammoids for the undirected case. In a directed graph \(D=(V,F)\), we say that \(X\subseteq V\) is linked into \(Y\subseteq V\), if there exists a set of mutually disjoint paths in \(D\), whose set of the initial vertices is \(X\) and whose set of the terminal vertices is a subset of \(Y\). Given \(A\), \(B\subseteq V\), the collection of all subsets of \(A\), which can be linked into \(B\), is a special type of matroid, known as a gammoid. In the case when \(A=V\), the gammoid is said to be strict. This concept translates naturally to an undirected graph \(G\). One can either replace paths by undirected paths, in the definitions, or one can regard \(G\) as a directed graph, in which each of its edges \(\{u,v\}\) is replaced by two directed edges \(uv\) and \(vu\). This latter comment was made by Woodall and he called (strict) gammoids arising from undirected graphs, undirected (strict) gammoids. Woodall gave an example of a strict gammoid, which was not an undirected gammoid, and, in this note, we exhibit a minimal such example and, in passing, we interpret the Ingleton and Piff's characterization of the strict gammoids for the undirected case.
0 references
strict gammoid
0 references