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