Decomposition tree of a lexicographic product of binary structures

作者：Ille P^*; Woodrow R E

来源：Discrete Mathematics, 2011, 311(21): 2346-2358.

DOI：10.1016/j.disc.2011.05.037

• Binary structure
• Decomposition tree
• Lexicographic product

Given a set S and a positive integer k, a binary structure is a function B : (S x S)\{(x, x); x is an element of S} -> {1, ... , k}. The set S is denoted by V (B) and the integer k is denoted by rk(B). With each subset X of V (B) associate the binary substructure B[X] of B induced by X defined by B[X](x, y) = B(x, y) for any x not equal y is an element of X. A subset X of V (B) is a clan of B if for any x, y is an element of X and v is an element of V (B) \ X, B(x, v) = B(y, v) and B(v, x) = B(v, y). A subset X of V (B) is a hyperclan of B if X is a clan of B satisfying: for every clan Y of B, if X boolean AND Y not equal theta, then X subset of Y or Y subset of X. With each binary structure B associate the family Pi (B) of the maximal proper and nonempty hyperclans under inclusion of B. The decomposition tree of a binary structure B is constituted by the hyperclans X of B such that Pi (B[X]) not equal theta and by the elements of Pi (B[X]). Given binary structures B and C such that rk(B) = rk(C), the lexicographic product Bleft perpendicularCright perpendicular of C by B is defined on V (B) x V (C) as follows. For any (x, y) not equal (x', y') is an element of V (B) x V (C), Bleft perpendicularCright perpendicular ((x. x'). (y, y')) = B(x, y) if x not equal y and left perpendicularCright perpendicular ((x, x'), (y, y')) = C(x', y') if x = y.

• 出版日期2011-11-6