Binding number and toughness for matching extension (Q1903741): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tough graphs and Hamiltonian circuits. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Toughness and matching extension in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Factorization of Linear Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The binding number of a graph and its Anderson number / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 08:49, 24 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Binding number and toughness for matching extension |
scientific article |
Statements
Binding number and toughness for matching extension (English)
0 references
13 May 1996
0 references
The binding number resp. the toughness of a simple graph \(G\) are defined by \[ \text{bind} (G) = \min \left\{ {\bigl |N_G(X) \bigr |\over |X |} : \varnothing \neq X \subset V(G) \text{ and } N_G(X) \neq V(G) \right\} \] resp. by \[ \text{tough} (G) = \min \left\{ {|X |\over w(G - X)} : X \subset V(G) \text{ and } w(G - X) \geq 2 \right\} \] where \(N_G(X)\) denotes the neighbor set of \(X\) in \(G\) and \(w(G - X)\) denotes the number of components of \(G - X\). Based on Tutte's 1-factor theorem, the author presents short proofs for the following result: Let \(G\) be a graph of even order and \(k \geq 1\). If \(\text{tough} (G) > k\) or \(\text{bind} (G) > \max \{k,(7k + 13)/12\}\) then every matching of size \(k\) in \(G\) can be extended to a 1-factor in \(G\). The case of \(\text{tough} (G) > k\) was settled earlier by \textit{M. D. Plummer} [Toughness and matching extension in graphs, Discrete Math. 72, No. 1-3, 311-320 (1988; 683.05034)] in a different way.
0 references
Tutte's theorem
0 references
binding number
0 references
toughness
0 references
neighbor set
0 references
number of components
0 references
matching
0 references
1-factor
0 references
matching extension
0 references