Conservative weightings and ear-decompositions of graphs
An ear-decomposition of a 2-edge-connected graph is defined as a sequence \(G_ 0,G_ 1,\ldots,G_ t=G\) of subgraphs of \(G\) such that \(G_ i\) arises from \(G_{i-1}\) by adding a path \(P_ i\), called ear, with end vertices in \(G_{i-1}\). The minimum number of ears with even length in an ear-decomposition is denoted as \(\varphi(G)\). There is a deep relation between ear-decompositions of \(G\) and the existence of an matching of \(G\). Let \(w:E\to\{-1,1\}\) be an edge-weighting of \(G\) such that \(w(C)\geq 0\) for every circuit \(C\) of \(G\). The maximum number of negative edges in such a weighting is denoted by \(\mu(G)\). The main result of the paper gives the following relation between \(\varphi(G)\) and \(\mu(G)\) \[ \mu(G)=(\varphi(G)+| V|-1)/2 \] where \(| V|\) is the number of vertices in \(G\).
- 2-Matchings and 2-covers of hypergraphs
- A Minimax Theorem for Directed Graphs
- A quick proof of Seymour's theorem on t-joins
- Covering directed and odd cuts
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 3211575 (Why is no real title available?)
- scientific article; zbMATH DE number 3231691 (Why is no real title available?)
- Matching, Euler tours and the Chinese postman
- On Odd Cuts and Plane Multicommodity Flows
- Paths, Trees, and Flowers
- Undirected distances and the postman-structure of graphs
- Maximality of the cycle code of a graph
- A generalization of Petersen's theorem
- Complexity of circuit intersection in graphs
- On a matroid defined by ear-decompositions of graphs
- Graft analogue of general Kotzig-Lovász decomposition
- Degree and regularity of Eulerian ideals of hypergraphs
- Joins, ears and Castelnuovo-Mumford regularity
- Approximating max-min weighted \(T\)-joins
- The edge-orientation problem and some of its variants on weighted graphs
- Disclosing barriers: a generalization of the canonical partition based on Lovász's formulation
- Circuit decompositions of join-covered graphs
- Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
- On combinatorial properties of binary spaces
- scientific article; zbMATH DE number 7150552 (Why is no real title available?)
- Associated primes of powers of edge ideals and ear decompositions of graphs
- Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
- Eulerian ideals
- On generalizations of matching-covered graphs
- Complexity of finding a join of maximum weight
- Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
- Decreasing behavior of the depth functions of edge ideals
- A general formula for the index of depth stability of edge ideals
- Basilica: new canonical decomposition in matching theory
- The covering radius of the cycle code of a graph
- Pseudo-Gorenstein edge rings and a new family of almost Gorenstein edge rings
- Irreducible decomposition of powers of edge ideals, computing dstab, astab.
This page was built for publication: Conservative weightings and ear-decompositions of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2367443)
