检索结果-南通市图书馆

Reconstruction of 2-Convex polyominoes with Non-Empty Corners

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Open Journal of Discrete Mathematics 2019年第4期9卷 83-109页

作者： Khalil Tawbe Salwa Mansour Department of Mathematics Lebanese UniversityBeirutLebanon Department of Mathematics The International University of BeirutBeirutLebanon Department of Mathematics Lebanese International UniversityBeirutLebanon.

This paper uses the theoretical material developed in a previous study by the authors in order to reconstruct a subclass of 2-convex polyominoes called where the upper left corner and the lower right corner of the polyomino contain each only one cell. The main idea is to control the shape of these polyominoes by using 32 types of geometries. Some modifications are made in the reconstruction algorithm of Chrobak and Dürr for HV-convex polyominoes in order to impose these geometries.

关键词： polyomino Convex Objects Monotone Path

Continuous Forcing Spectra of Even Polygonal Chains

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2021年第2期37卷 337-347页

作者： He-ping ZHANG Xiao-yan JIANG School of Mathematics and Statistics Lanzhou UniversityLanzhou 730000China School of Mathematics and Statistics Huizhou UniversityHuizhou 516007China

Let G be a graph that admits a perfect matching M.A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of *** cardinality of a forcing set of M with the smallest size is called the forcing number of M,denoted by f(G,M).The forcing spectrum of G is defined as:Spec(G)={f(G,M)|M is a perfect matching of G}.In this paper,by applying the Ztransformation graph(resonance graph)we show that for any polyomino with perfect matchings and any even polygonal chain,their forcing spectra are integral *** we obtain some sharp bounds on maximum and minimum forcing numbers of hexagonal chains with given number of *** spectra of two extremal chains are determined.

关键词： perfect matching forcing number forcing spectrum polyomino even polygonal chain Z-transformation graph

Signed Tilings by Ribbon L n-Ominoes, n Even, via Gröbner Bases

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

Open Journal of Discrete Mathematics 2016年第3期6卷 185-206页

作者： Kenneth Gill Viorel Nitica Department of Mathematics West Chester University West Chester USA

Let Tn be the set of ribbon L-shaped n-ominoes for some n≥4 even, and let T+n be Tn with an extra 2 x 2 square. We investigate signed tilings of rectangles by Tn and T+n . We show that a rectangle has a signed tiling by Tn if and only if both sides of the rectangle are even and one of them is divisible by n, or if one of the sides is odd and the other side is divisible by . We also show that a rectangle has a signed tiling by T+n, n≥6 even, if and only if both sides of the rectangle are even, or if one of the sides is odd and the other side is divisible by . Our proofs are based on the exhibition of explicit GrÖbner bases for the ideals generated by polynomials associated to the tiling sets. In particular, we show that some of the regular tiling results in Nitica, V. (2015) Every tiling of the first quadrant by ribbon L n-ominoes follows the rectangular pattern. Open Journal of Discrete Mathematics, 5, 11-25, cannot be obtained from coloring invariants.

关键词： polyomino Replicating Tile L-Shaped polyomino Skewed L-Shaped polyomino Signed Tilings Gröbner Basis Tiling Rectangles Coloring Invariants

Revisiting a Tiling Hierarchy (II)

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Open Journal of Discrete Mathematics 2018年第2期8卷 48-63页

作者： Viorel Nitica Department of Mathematics West Chester University West Chester PA USA

In a recent paper, we revisited Golomb’s hierarchy for tiling capabilities of finite sets of polyominoes. We considered the case when only translations are allowed for the tiles. In this classification, for several levels in Golomb’s hierarchy, more types appear. We showed that there is no general relationship among tiling capabilities for types corresponding to same level. Then we found the relationships from Golomb’s hierarchy that remain valid in this setup and found those that fail. As a consequence we discovered two alternative tiling hierarchies. The goal of this note is to study the validity of all implications in these new tiling hierarchies if one replaces the simply connected regions by deficient ones. We show that almost all of them fail. If one refines the hierarchy for tile sets that tile rectangles and for deficient regions then most of the implications of tiling capabilities can be recovered.

关键词： Tiling polyomino Deficient Region Tile Set Tiling Hierarchy

Every Tiling of the First Quadrant by Ribbon <i>L n</i>-Ominoes Follows the Rectangular Pattern

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Open Journal of Discrete Mathematics 2015年第2期5卷 11-25页

作者： Viorel Nitica Department of Mathematics West Chester University West Chester USA

Let and let be the set of four ribbon L-shaped n-ominoes. We study tiling problems for regions in a square lattice by . Our main result shows a remarkable property of this set of tiles: any tiling of the first quadrant by , n even, reduces to a tiling by and rectangles, each rectangle being covered by two ribbon L-shaped n-ominoes. An application of our result is the characterization of all rectangles that can be tiled by , n even: a rectangle can be tiled by , n even, if and only if both of its sides are even and at least one side is divisible by n. Another application is the existence of the local move property for an infinite family of sets of tiles: , n even, has the local move property for the class of rectangular regions with respect to the local moves that interchange a tiling of an square by n/2 vertical rectangles, with a tiling by n/2 horizontal rectangles, each vertical/horizontal rectangle being covered by two ribbon L-shaped n-ominoes. We show that none of these results are valid for any odd n. The rectangular pattern of a tiling of the first quadrant persists if we add an extra tile to , n even. A rectangle can be tiled by the larger set of tiles if and only if it has both sides even. We also show that our main result implies that a skewed L-shaped n-omino, n even, is not a replicating tile of order k2 for any odd k.

关键词： polyomino Replicating Tile L-Shaped polyomino Skewed L-Shaped polyomino Local Move Property Tiling Rectangles Rectangular Pattern Tiling First Quadrant

Signed Tilings by Ribbon L n-Ominoes, n Odd, via Gröbner Bases

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Open Journal of Discrete Mathematics 2016年第4期6卷 297-313页

作者： Viorel Nitica Department of Mathematics West Chester University West Chester PA USA

We show that a rectangle can be signed tiled by ribbon L n-ominoes, n odd, if and only if it has a side divisible by n. A consequence of our technique, based on the exhibition of an explicit Gröbner basis, is that any k-inflated copy of the skewed L n-omino has a signed tiling by skewed L n-ominoes. We also discuss regular tilings by ribbon L n-ominoes, n odd, for rectangles and more general regions. We show that in this case obstructions appear that are not detected by signed tilings.

关键词： polyomino Replicating Tile L-Shaped polyomino Skewed L-Shaped polyomino Signed Tilings Gröbner Basis Coloring Invariants

On Tilings of Quadrants and Rectangles and Rectangular Pattern

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Open Journal of Discrete Mathematics 2016年第4期6卷 351-371页

作者： Viorel Nitica Department of Mathematics West Chester University of Pennsylvania West Chester PA USA

The problem of tiling rectangles by polyominoes generated large interest. A related one is the problem of tiling parallelograms by twisted polyominoes. Both problems are related with tilings of (skewed) quadrants by polyominoes. Indeed, if all tilings of a (skewed) quadrant by a tile set can be reduced to a tiling by congruent rectangles (parallelograms), this provides information about tilings of rectangles (parallelograms). We consider a class of tile sets in a square lattice appearing from arbitrary dissections of rectangles in two L-shaped polyominoes and from symmetries of these tiles about the first bisector. Only translations of the tiles are allowed in a tiling. If the sides of the dissected rectangle are coprime, we show the existence of tilings of all (skewed) quadrants that do not follow the rectangular (parallelogram) pattern. If one of the sides of the dissected rectangle is 2 and the other is odd, we also show tilings of rectangles by the tile set that do not follow the rectangular pattern. If one of the sides of the dissected rectangle is 2 and the other side is even, we show a new infinite family of tile sets that follows the rectangular pattern when tiling one of the quadrants. For this type of dis-section, we also show a new infinite family that does not follow the rectangular pattern when tiling rectangles. Finally, we investigate more general dissections of rectangles, with. Here we show infinite families of tile sets that follow the rectangular pattern for a quadrant and infinite families that do not follow the rectangular pattern for any quadrant. We also show, for infinite families of tile sets of this type, tilings of rectangles that do not follow the rectangular pattern.

关键词： polyomino L-Shaped polyomino Skewed L-Shaped polyomino Tiling Rectangles Tiling Quadrants Tiling Parallelograms Rectangular Pattern for Tiling Quadrants/Rectangles