The connectivity of \(Z\)-transformation graphs of perfect matchings of polyominoes (Q1815325)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 943232
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The connectivity of \(Z\)-transformation graphs of perfect matchings of polyominoes |
scientific article; zbMATH DE number 943232 |
Statements
The connectivity of \(Z\)-transformation graphs of perfect matchings of polyominoes (English)
0 references
17 August 1997
0 references
Let \(G\) be a plane graph. The \(Z\)-transformation graph \(Z(G)\) of \(G\) is the graph whose vertices are the perfect matchings of \(G\) with two vertices being adjacent if and only if the symmetric difference of the corresponding perfect matchings consists of the boundary of a single finite face of \(G\). The author discusses some properties of polyominoes with perfect matchings. In particular, he proves that outside of two exceptional cases the connectivity of the \(Z\)-transformation graph of a polyomino with perfect matchings has connectivity equal to its minimum degree.
0 references
polyomino
0 references
\(Z\)-transformation graph
0 references
perfect matching
0 references
0.93720376
0 references
0.90923834
0 references
0.8988709
0 references
0 references
0.89195126
0 references
0 references
0.8879555
0 references
0.88487935
0 references
