The connectivity of \(Z\)-transformation graphs of perfect matchings of polyominoes
type: Item
instance of: scholarly article
title: The connectivity of \(Z\)-transformation graphs of perfect matchings of polyominoes
zbMATH Open document ID: 0869.05022
DOI: 10.1016/0012-365X(95)00048-2
author: Heping Zhang
published in: Discrete Mathematics
publication date: 1997-08-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B50
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 943232
zbMATH Keywords: polyomino
zbMATH Keywords: \(Z\)-transformation graph
zbMATH Keywords: perfect matching
reviewed by: Brian Alspach
MaRDI profile type: Publication
cites work: Combinatorial properties of polyominoes
cites work: Chessboard domination problems
cites work: On the queen domination problem
cites work: On some counting polynomials in chemistry
cites work: Q5581642
cites work: Matching theory
cites work: Q4123364
cites work: King and domino polynomials for polyomino graphs
cites work: When each hexagon of a hexagonal system covers it
cites work: Z-transformation graphs of perfect matchings of hexagonal systems
cites work: The connectivity of Z-transformation graphs of perfect matchings of hexagonal systems
cites work: Plane elementary bipartite graphs
Wikidata QID: Q127908925
Recommended article: The connectivity of Z-transformation graphs of perfect matchings of hexagonal systems
Recommended article: \(Z\)-transformation graphs of perfect matchings of plane bipartite graphs
Recommended article: Q4246045
Recommended article: Q5310101
Recommended article: Perfect matchings of polyomino graphs
Recommended article: Total Z-transformation graphs of perfect matching of plane bipartite graphs
Recommended article: Z-transformation graphs of perfect matchings of hexagonal systems
Recommended article: Perfect matchings of generalized polyomino graphs
Recommended article: \(Z\)-transformation graphs of maximum matchings of plane bipartite graphs
Recommended article: Q4552267
description: scientific article; zbMATH DE number 943232