Toughness and matching extension in graphs (Q1824634): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tough graphs and Hamiltonian circuits. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3215240 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Paths, Trees, and Flowers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Brick decompositions and the matching rank of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Toughness and the existence ofk-factors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5520564 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5508779 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3267903 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5329577 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of factorizable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matching theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On n-extendable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4732491 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3800093 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5202207 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matching extension and the genus of a graph / rank | |||
Normal rank |
Latest revision as of 11:02, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Toughness and matching extension in graphs |
scientific article |
Statements
Toughness and matching extension in graphs (English)
0 references
1988
0 references
The author gives two results connecting the toughness of a graph with its matching extendability. Let G be a graph with a perfect matching, G is said to be n-extendable if every matching of size n in G extends to a perfect matching. The toughness of G, denoted tough(G), is the minimum over all vertex cutsets S of the quantity \(| S| /c(G-s)\) where c(G-S) is the number of components of G-S. The author proves the following results: 1. If \(tough(G)>n\), a positive integer, then G is n- extendable. 2. If G has p vertices, G is n-extendable, and \(tough(G)<1\) then \(n\leq (p-2)/6\).
0 references
matching extendability
0 references
toughness
0 references