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
    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

    Identifiers