Matching extension and the genus of a graph (Q1107545)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Matching extension and the genus of a graph |
scientific article; zbMATH DE number 4065039
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Matching extension and the genus of a graph |
scientific article; zbMATH DE number 4065039 |
Statements
Matching extension and the genus of a graph (English)
0 references
1988
0 references
A connected graph G of order p and having a perfect matching (a spanning, 1-regular subgraph) is said to be n-extendable (where n is a positive integer, with \(n\leq (p-2)/2)\) if every matching in G of size n is a subset of a perfect matching. The main result of the present paper is: If G is any connected graph, with genus \(\gamma >0\), then (a) G is not \((\lfloor 9/2+18(\gamma -1)/(7+\sqrt{48\gamma -47})\rfloor)\)-extendable; (b) if, in addition, G has no 3-cycles, then G is not \((2+\lfloor 2\sqrt{\gamma})\)-extendable.
0 references
extendable graphs
0 references
perfect matching
0 references
genus
0 references
0 references
0.93622994
0 references
0.93443525
0 references
0.91956955
0 references
0.9162721
0 references
0.9149956
0 references
