A polyomino P is called L-convex if for every two cells there exists a monotone path included in P with at most one change of direction. This paper is a theoretical step for the reconstruction of all L-convex polyomin...A polyomino P is called L-convex if for every two cells there exists a monotone path included in P with at most one change of direction. This paper is a theoretical step for the reconstruction of all L-convex polyominoes by using the geometrical paths. First we investigate the geometrical properties of all subclasses of non-directed L-convex polyominoes by giving nine geometries that characterize all non-directed L-convex polyominoes. Finally, we study the subclasses of directed L-convex polyominoes and we give necessary and sufficient conditions for polyominoes to be L-convex.展开更多
This paper uses the geometrical properties of L-convex polyominoes in order to reconstruct these polyominoes. The main idea is to modify some clauses to the original construction of Chrobak and Dürr in order to c...This paper uses the geometrical properties of L-convex polyominoes in order to reconstruct these polyominoes. The main idea is to modify some clauses to the original construction of Chrobak and Dürr in order to control the L-convexity using 2SAT satisfaction problem.展开更多
A polyomino P is called 2-convex if for every two cells there exists a monotone path included in P with at most two changes of direction. This paper studies the geometrical properties of a sub-class of 2-convex polyom...A polyomino P is called 2-convex if for every two cells there exists a monotone path included in P with at most two changes of direction. This paper studies the geometrical properties of a sub-class of 2-convex polyominoes called where the upper left corner and the lower right corner of the polyomino each contains only one cell.展开更多
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 pol...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.展开更多
Let Q_n and B_n denote a quasi-polyomino chain with n squares and a quasi-hexagonalchain with n hexagons,respectively.In this paper,the authors establish a relation between the Wienernumbers of Q_n and B_n:W(Q_n)=1/4[...Let Q_n and B_n denote a quasi-polyomino chain with n squares and a quasi-hexagonalchain with n hexagons,respectively.In this paper,the authors establish a relation between the Wienernumbers of Q_n and B_n:W(Q_n)=1/4[W(B_n)-8/3n^3+(14)/3n+3].And the extremal quasi-polyominochains with respect to the Wiener number are determined.Furthermore,several classes of polyominochains with large Wiener numbers are ordered.展开更多
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 p...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.展开更多
Let T<sub>n </sub>be the set of ribbon L-shaped n-ominoes for some n≥4 even, and let T<sup>+</sup><sub>n</sub> be T<sub>n</sub> with an extra 2 x 2 square. We investiga...Let T<sub>n </sub>be the set of ribbon L-shaped n-ominoes for some n≥4 even, and let T<sup>+</sup><sub>n</sub> be T<sub>n</sub> with an extra 2 x 2 square. We investigate signed tilings of rectangles by T<sub>n</sub> and T<sup>+</sup><sub>n</sub> . We show that a rectangle has a signed tiling by T<sub>n</sub> 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<sup>+</sup><sub>n, </sub> 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.展开更多
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...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.展开更多
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 quadran...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.展开更多
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 l...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.展开更多
In theoretical chemistry, the researchers use graph models to express the structure of molecular, and the Zagreb indices and multiplicative Zagreb indices defined on molecular graph G are applied to measure the chemic...In theoretical chemistry, the researchers use graph models to express the structure of molecular, and the Zagreb indices and multiplicative Zagreb indices defined on molecular graph G are applied to measure the chemical characteristics of compounds and drugs. In this paper, we present the exact expressions of multiplicative Zagreb indices for certain important chemical structures like nanotube, nanostar and polyomino chain.展开更多
文摘A polyomino P is called L-convex if for every two cells there exists a monotone path included in P with at most one change of direction. This paper is a theoretical step for the reconstruction of all L-convex polyominoes by using the geometrical paths. First we investigate the geometrical properties of all subclasses of non-directed L-convex polyominoes by giving nine geometries that characterize all non-directed L-convex polyominoes. Finally, we study the subclasses of directed L-convex polyominoes and we give necessary and sufficient conditions for polyominoes to be L-convex.
文摘This paper uses the geometrical properties of L-convex polyominoes in order to reconstruct these polyominoes. The main idea is to modify some clauses to the original construction of Chrobak and Dürr in order to control the L-convexity using 2SAT satisfaction problem.
文摘A polyomino P is called 2-convex if for every two cells there exists a monotone path included in P with at most two changes of direction. This paper studies the geometrical properties of a sub-class of 2-convex polyominoes called where the upper left corner and the lower right corner of the polyomino each contains only one cell.
文摘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.
基金supported by the Natural Science Foundation of China under Grant No. 10371102
文摘Let Q_n and B_n denote a quasi-polyomino chain with n squares and a quasi-hexagonalchain with n hexagons,respectively.In this paper,the authors establish a relation between the Wienernumbers of Q_n and B_n:W(Q_n)=1/4[W(B_n)-8/3n^3+(14)/3n+3].And the extremal quasi-polyominochains with respect to the Wiener number are determined.Furthermore,several classes of polyominochains with large Wiener numbers are ordered.
文摘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.
文摘Let T<sub>n </sub>be the set of ribbon L-shaped n-ominoes for some n≥4 even, and let T<sup>+</sup><sub>n</sub> be T<sub>n</sub> with an extra 2 x 2 square. We investigate signed tilings of rectangles by T<sub>n</sub> and T<sup>+</sup><sub>n</sub> . We show that a rectangle has a signed tiling by T<sub>n</sub> 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<sup>+</sup><sub>n, </sub> 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.
文摘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.
文摘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.
文摘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.
文摘In theoretical chemistry, the researchers use graph models to express the structure of molecular, and the Zagreb indices and multiplicative Zagreb indices defined on molecular graph G are applied to measure the chemical characteristics of compounds and drugs. In this paper, we present the exact expressions of multiplicative Zagreb indices for certain important chemical structures like nanotube, nanostar and polyomino chain.
