Graphic matroid – Knowledge and References

Explore chapters and articles related to this topic

Computational techniques

Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022

As an example, if Nd is the graphic matroid of an m-cycle with one edge replaced by two edges in parallel, one of which is d, then M(Cn)⊗Nd is the graphic matroid of a flower graph (see Figure 7.4(b)). In this example, T(Nd\d;x,y)=Pm(x,y) and T(Nd/d;x,y)=yPm−1(x,y), where Pn(x,y)=T(Cn;x,y). Thus, the Tutte polynomial of flower graphs can be obtained by substituting f=Pm−1(x,y)+1−y and g=Pm−1(x,y)+1 in (7.14). An alternative method using a linear recurrence may be found in [869].

Biobjective optimization problems on matroids with binary costs

View Article

Journal Information

Published in Optimization, 2023

Jochen Gorski, Kathrin Klamroth, Julia Sudhoff

Recall from Section 3 that the objective values of the binary objective b can only take values between 0 and m, i.e. , where m is the rank of the underlying matroid and B is an arbitrary basis. As a consequence, we have that . For an instance of the graphic matroid on a connected graph with n vertices and m edges, this implies that for all spanning trees T of G. Note that due to the common notation that and for graphic matroids, the rank of a graphic matroid is thus n−1. The CE approach determines all efficient spanning trees by maintaining a list with n entries, one for each potential value of that stores the currently best cost value together with all corresponding trees that were enumerated so far.