Local move connectedness of domino tilings with diagonal impurities

Fuminiko Nakano; Hirotaka Ono; Taizo Sadahiro

doi:10.1016/j.disc.2010.02.015

Local move connectedness of domino tilings with diagonal impurities

Fuminiko Nakano, Hirotaka Ono, Taizo Sadahiro

mathematics and information

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

We study the perfect matchings in the dual of the square-octagon lattice graph, which can be considered as domino tilings with impurities in some sense. In particular, we show the local move connectedness, that is, if G is a vertex induced finite subgraph which is simply connected, then any perfect matching in G can be transformed into any other perfect matching in G by applying a sequence of local moves each of which involves only two edges.

Original language	English
Pages (from-to)	1918-1931
Number of pages	14
Journal	Discrete Mathematics
Volume	310
Issue number	13-14
DOIs	https://doi.org/10.1016/j.disc.2010.02.015
Publication status	Published - Jul 28 2010

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2010.02.015

Cite this

@article{0d0d5f8653be4491952a6dd7de95106e,

title = "Local move connectedness of domino tilings with diagonal impurities",

abstract = "We study the perfect matchings in the dual of the square-octagon lattice graph, which can be considered as domino tilings with impurities in some sense. In particular, we show the local move connectedness, that is, if G is a vertex induced finite subgraph which is simply connected, then any perfect matching in G can be transformed into any other perfect matching in G by applying a sequence of local moves each of which involves only two edges.",

author = "Fuminiko Nakano and Hirotaka Ono and Taizo Sadahiro",

year = "2010",

month = jul,

day = "28",

doi = "10.1016/j.disc.2010.02.015",

language = "English",

volume = "310",

pages = "1918--1931",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "13-14",

}

TY - JOUR

T1 - Local move connectedness of domino tilings with diagonal impurities

AU - Nakano, Fuminiko

AU - Ono, Hirotaka

AU - Sadahiro, Taizo

PY - 2010/7/28

Y1 - 2010/7/28

N2 - We study the perfect matchings in the dual of the square-octagon lattice graph, which can be considered as domino tilings with impurities in some sense. In particular, we show the local move connectedness, that is, if G is a vertex induced finite subgraph which is simply connected, then any perfect matching in G can be transformed into any other perfect matching in G by applying a sequence of local moves each of which involves only two edges.

AB - We study the perfect matchings in the dual of the square-octagon lattice graph, which can be considered as domino tilings with impurities in some sense. In particular, we show the local move connectedness, that is, if G is a vertex induced finite subgraph which is simply connected, then any perfect matching in G can be transformed into any other perfect matching in G by applying a sequence of local moves each of which involves only two edges.

UR - http://www.scopus.com/inward/record.url?scp=77951120462&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951120462&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2010.02.015

DO - 10.1016/j.disc.2010.02.015

M3 - Article

AN - SCOPUS:77951120462

SN - 0012-365X

VL - 310

SP - 1918

EP - 1931

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 13-14

ER -

Local move connectedness of domino tilings with diagonal impurities

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this