FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2008, VOLUME 14, NUMBER 4, PAGES 137-149

Matrices and graphs of essential dependence of proper families of functions

A. A. Kozlov
V. A. Nosov
A. E. Pankratiev

Abstract

View as HTML     View as gif image

This paper considers proper families of functions, which are used in functional specification of Latin squares of large size over the set of $n$-dimensional binary vectors. Proper families of functions are studied from the viewpoint of the intrinsic structure of the corresponding graphs of essential dependence and their adjacency matrices. Various necessary and sufficient conditions for a binary matrix to be treated as the adjacency matrix of the graph of essential dependence of a proper family of functions are derived. Also, transformations of matrices are considered, under which the indicated property is preserved. It is demonstrated that any directed graph without loops and multiple edges can be embedded as an induced subgraph into the graph of essential dependence of some proper family of functions. Moreover, such embedding is reasonably economical and the functions of the resulting proper family inherit properties of the functions that realize the original graph as the graph of essential dependence.

Location: http://mech.math.msu.su/~fpm/eng/k08/k084/k08408h.htm
Last modified: February 26, 2009