کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4598919 1631110 2015 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A (0,1)(0,1)-matrix existence theorem and equivalent tiling problems with dimers and monomers
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
A (0,1)(0,1)-matrix existence theorem and equivalent tiling problems with dimers and monomers
چکیده انگلیسی

Let R=(r1,r2,…,rm)R=(r1,r2,…,rm) and S=(s1,s2,…,sn)S=(s1,s2,…,sn) be nonnegative integral vectors. The class A1(R,S)A1(R,S) of (0,1)(0,1)-matrices with row sum vector R, column sum vector S  , and no two consecutive 1's in any column is introduced. Matrices in this class correspond to certain tilings of rectangles by vertical dimers and monomers and arise in the inverse eigenvalue problem for graphs. The main theorem gives necessary and sufficient conditions for the class A1(R,S)A1(R,S) to be nonempty. The conditions can be expressed as a system of majorizations in the spirit of the Gale–Ryser theorem. The class A1(R,S)A1(R,S) is associated with a type of interchange graph, which is proved to be connected. Also, in the case when A1(R,S)A1(R,S) contains a single matrix, the structure of this matrix is identified.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 485, 15 November 2015, Pages 503–526
نویسندگان
, ,