Computing the degree of some matchings in a graph
Let \(G\) be a connected graph. A matching \(M\) in \(G\) is a set of edges of \(G\) without two of them adjacent (having a common vertex). The graph whose vertices are the matchings in \(G\) and two matchings \(M\) and \(N\) are adjacent if and only if \( (M\setminus N)\cup (N\setminus M)\) is the...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Journal of Combinatorics
2024-10-01
|
| Series: | The American Journal of Combinatorics |
| Subjects: | |
| Online Access: | https://ajcombinatorics.org/ojs/index.php/AmJC/article/view/17 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Let \(G\) be a connected graph. A matching \(M\) in \(G\) is a set of edges of \(G\) without two of them adjacent (having a common vertex). The graph whose vertices are the matchings in \(G\) and two matchings \(M\) and \(N\) are adjacent if and only if \( (M\setminus N)\cup (N\setminus M)\) is the edge set of a path or a cycle, is denoted by \({\cal G}({\cal M}(G))\) and called the skeleton of the matching polytope of \(G\). The degree of a matching \(M\) in \(G\) is the degree of the vertex \(M\) in \({\cal G}({\cal M}(G))\). In the literature some authors have studied the degree of some matchings, in particular when \(G\) is a tree. In this paper we continue this study and we present some formulas to compute the degree of a matching \(M\) in a graph with cycles. More explicitly, we focus on the matchings having \(1\) or \(2\) edges and on the matchings of more than two edges with some constraints.
|
|---|---|
| ISSN: | 2768-4202 |