کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654684 1632824 2009 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The minimum cardinality of maximal systems of rectangular islands
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The minimum cardinality of maximal systems of rectangular islands
چکیده انگلیسی

For given positive integers mm and nn, and R={(x,y):0≤x≤m and 0≤y≤n}R={(x,y):0≤x≤m and 0≤y≤n}, a set HH of rectangles that are all subsets of RR and the vertices of which have integer coordinates is called a system of rectangular islands if for every pair of rectangles in HH one of them contains the other or they do not overlap at all. Let IRIR denote the ordered set of systems of rectangular islands on RR, and let max(IR)max(IR) denote the maximal elements of IRIR. For f(m,n)=max{|H|:H∈max(IR)}f(m,n)=max{|H|:H∈max(IR)}, G. Czédli [G. Czédli, The number of rectangular islands by means of distributive lattices, European J. Combin. 30 (1) (2009) 208–215)] proved f(m,n)=⌊(mn+m+n−1)/2⌋f(m,n)=⌊(mn+m+n−1)/2⌋. For g(m,n)=min{|H|:H∈max(IR)}g(m,n)=min{|H|:H∈max(IR)}, we prove g(m,n)=m+n−1g(m,n)=m+n−1. We also show that for any integer hh in the interval [g(m,n),f(m,n)][g(m,n),f(m,n)], there exists an H∈max(IR)H∈max(IR) such that |H|=h|H|=h.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 30, Issue 1, January 2009, Pages 216–219
نویسندگان
,