Computing the degree of some matchings in a graph
American Journal of Combinatorics · 2024
DOI: 10.63151/amjc.v3i.17 ↗Kurz gefasst
Fachartikel in der Zeitschrift American Journal of Combinatorics, 2024. Verfasst von Rosário Fernandes. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Fernandes, R. (2024). Computing the degree of some matchings in a graph. American Journal of Combinatorics. https://doi.org/10.63151/amjc.v3i.17
Vancouver
Fernandes R. Computing the degree of some matchings in a graph. American Journal of Combinatorics. 2024. doi:10.63151/amjc.v3i.17
BibTeX
@article{Fernandes2024,
author = {Fernandes, Rosário},
title = {Computing the degree of some matchings in a graph},
journal = {American Journal of Combinatorics},
year = {2024},
doi = {10.63151/amjc.v3i.17}
}
EUVIMED