Results 11 to 20 of about 759 (82)
Geometric bijections between spanning subgraphs and orientations of a graph
Journal of the London Mathematical Society, Volume 108, Issue 3, Page 1082-1120, September 2023., 2023 Abstract Let G$G$ be a connected finite graph. Backman, Baker, and Yuen have constructed a family of explicit and easy‐to‐describe bijections between spanning trees of G$G$ and (σ,σ∗)$(\sigma ,\sigma ^*)$‐compatible orientations, where the (σ,σ∗)$(\sigma ,\sigma ^*)$‐compatible orientations are the representatives of equivalence classes of orientations
Changxin Ding
wiley +1 more source
On generalisations of the Aharoni–Pouzet base exchange theorem
Bulletin of the London Mathematical Society, Volume 55, Issue 3, Page 1540-1549, June 2023., 2023 Abstract The Greene–Magnanti theorem states that if M$ M$ is a finite matroid, B0$ B_0$ and B1$ B_1$ are bases and B0=⋃i=1nXi$ B_0=\bigcup _{i=1}^{n} X_i$ is a partition, then there is a partition B1=⋃i=1nYi$ B_1=\bigcup _{i=1}^{n}Y_i$ such that (B0∖Xi)∪Yi$ (B_0 \setminus X_i) \cup Y_i$ is a base for every i$ i$. The special case where each Xi$ X_i$ is
Zsuzsanna Jankó, Attila Joó
wiley +1 more source
Regular Matroids with Graphic Cocircuits [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 We introduce the notion of graphic cocircuits and show that a large class of regular matroids with graphic cocircuits belongs to the class of signed-graphic matroids. Moreover, we provide an algorithm which determines whether a cographic matroid with graphic cocircuits is signed-graphic or not.
Konstantinos Papalamprou +1 more
openaire +3 more sources
Small Cocircuits in Minimally Vertically 4-Connected Matroids
SIAM Journal on Discrete Mathematics, 2022 Halin proved that every minimally $k$-connected graph has a vertex of degree $k$. More generally, does every minimally vertically $k$-connected matroid have a $k$-element cocircuit? Results of Murty and Wong give an affirmative answer when $k \le 3$.
Oxley, James, Walsh, Zach
openaire +3 more sources
Diameters of Cocircuit Graphs of Oriented Matroids: An Update [PDF]
The Electronic Journal of Combinatorics, 2021 Oriented matroids are combinatorial structures that generalize point configurations, vector configurations, hyperplane arrangements, polyhedra, linear programs, and directed graphs. Oriented matroids have played a key role in combinatorics, computational geometry, and optimization. This paper surveys prior work and presents an update on the search for
Adler, Ilan +3 more
openaire +3 more sources
Short Cocircuits in Binary Matroids
European Journal of Combinatorics, 1987 The authors' summary: ``Given a simple graph G having vertex set V, it is obvious that for any spanning tree T, there is an edge of T whose fundamental cutset has size at most \(| V| -1\). We extend this result to matroids. Call a cocircuit of a matroid M short if its size is at most the rank of M.
Bixby, Robert E., Cunningham, William H.
openaire +1 more source
On Density-Critical Matroids [PDF]
, 2019 For a matroid $M$ having $m$ rank-one flats, the density $d(M)$ is $\tfrac{m}{r(M)}$ unless $m = 0$, in which case $d(M)= 0$. A matroid is density-critical if all of its proper minors of non-zero rank have lower density.
Campbell, Rutger +3 more
core +3 more sources
The Tutte Polynomial of Some Matroids
International Journal of Combinatorics, Volume 2012, Issue 1, 2012., 2012 The Tutte polynomial of a graph or a matroid, named after W. T. Tutte, has the important universal property that essentially any multiplicative graph or network invariant with a deletion and contraction reduction must be an evaluation of it. The deletion and contraction operations are natural reductions for many network models arising from a wide range
Criel Merino +3 more
wiley +1 more source
A Characterization of Uniform Matroids
International Scholarly Research Notices, Volume 2011, Issue 1, 2011., 2011 This paper gives a characterization of uniform matroids by means of locked subsets. Locked subsets are 2‐connected subsets, their complements are 2‐connected in the dual, and the minimum rank of both is 2. Locked subsets give the nontrivial facets of the bases polytope.
Brahim Chaourar, A. Jaballah
wiley +1 more source
On the Number of Circuit-cocircuit Reversal Classes of an Oriented Matroid [PDF]
, 2018 The first author introduced the circuit-cocircuit reversal system of an oriented matroid, and showed that when the underlying matroid is regular, the cardinalities of such system and its variations are equal to special evaluations of the Tutte polynomial
Gioan, Emeric, Yuen, Chi Ho
core +3 more sources