• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 2
  • Tagged with
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Even Cycle and Even Cut Matroids

Pivotto, Irene January 2011 (has links)
In this thesis we consider two classes of binary matroids, even cycle matroids and even cut matroids. They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes of matroids. We first consider the Isomorphism Problem, that is the relation between two representations of the same matroid. A representation of an even cycle matroid is a pair formed by a graph together with a special set of edges of the graph. Such a pair is called a signed graph. A representation for an even cut matroid is a pair formed by a graph together with a special set of vertices of the graph. Such a pair is called a graft. We show that two signed graphs representing the same even cycle matroid relate to two grafts representing the same even cut matroid. We then present two classes of signed graphs and we solve the Isomorphism Problem for these two classes. We conjecture that any two representations of the same even cycle matroid are either in one of these two classes, or are related by a local modification of a known operation, or form a sporadic example. The second problem we consider is finding the excluded minors for these classes of matroids. A difficulty when looking for excluded minors for these classes arises from the fact that in general the matroids may have an arbitrarily large number of representations. We define degenerate even cycle and even cut matroids. We show that a 3-connected even cycle matroid containing a 3-connected non-degenerate minor has, up to a simple equivalence relation, at most twice as many representations as the minor. We strengthen this result for a particular class of non-degenerate even cycle matroids. We also prove analogous results for even cut matroids.
2

Even Cycle and Even Cut Matroids

Pivotto, Irene January 2011 (has links)
In this thesis we consider two classes of binary matroids, even cycle matroids and even cut matroids. They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes of matroids. We first consider the Isomorphism Problem, that is the relation between two representations of the same matroid. A representation of an even cycle matroid is a pair formed by a graph together with a special set of edges of the graph. Such a pair is called a signed graph. A representation for an even cut matroid is a pair formed by a graph together with a special set of vertices of the graph. Such a pair is called a graft. We show that two signed graphs representing the same even cycle matroid relate to two grafts representing the same even cut matroid. We then present two classes of signed graphs and we solve the Isomorphism Problem for these two classes. We conjecture that any two representations of the same even cycle matroid are either in one of these two classes, or are related by a local modification of a known operation, or form a sporadic example. The second problem we consider is finding the excluded minors for these classes of matroids. A difficulty when looking for excluded minors for these classes arises from the fact that in general the matroids may have an arbitrarily large number of representations. We define degenerate even cycle and even cut matroids. We show that a 3-connected even cycle matroid containing a 3-connected non-degenerate minor has, up to a simple equivalence relation, at most twice as many representations as the minor. We strengthen this result for a particular class of non-degenerate even cycle matroids. We also prove analogous results for even cut matroids.

Page generated in 0.0673 seconds