Article
Homomorphisms of binary Cayley graphs.
A binary Cayley graph is a Cayley graph based on a binary group. In 1992, Payan proved that any non-bipartite binary Cayley graph must contain a generalized Mycielski graph of an odd cycle, implying that such a graph cannot have chromatic number 3.
We strengthen this result first by proving that any non-bipartite binary Cayley graph must contain a projective cube as a subgraph. We further conjecture that any homomorphism of a non-bipartite binary Cayley graph to a projective cube must be surjective and we prove a special case of this conjecture.
A signed graph is a graph and a subset of its edges which corresponds to an assignment of signs to the edges: edges in are negative while edges not in are positive. A closed walk of a signed graph is balanced if the product of the signs of its edges (repetitions included) is positive, and unbalanced otherwise. The unbalanced-girth of a signed graph is the length of a shortest unbalanced closed walk (if such a walk exists). A homomorphism of to is a homomorphism of to
which preserves the balance of closed walks.
In this work, given a signed bipartite graph
of unbalanced-girth , we give a necessary and sufficient condition for to admit a homomorphism from any signed bipartite graph of unbalanced-girth at least whose underlying graph is -minor-free. The condition can be checked in polynomial time with respect to the order of
.
Let
be the signed bipartite graph on vertex set where vertices and are adjacent with a positive edge if their difference is in (where the ’s form the standard basis), and adjacent with a negative edge if their difference is (that is, the all-1 vector). As an application of our work, we prove that every signed bipartite -minor-free graph of unbalanced-girth admits a homomorphism to . This supports a conjecture of Guenin claiming that every signed bipartite planar graph of unbalanced-girth admits a homomorphism to
(this would be an extension of the four-color theorem).
We also give an application of our work to edge-coloring
-regular -minor-free multigraphs.
In this article, the feasibility of realization of optimal circulant topologies in networks-on-chip was researched. The software for automating the synthesis of circulant topologies of various dimensions and of any number of generatrices is presented. The implemented methods to speed up the synthesis process, based on the properties of circulants, as well as improving the algorithm for calculation of the distance between nodes and caching the adjacency matrix to achieve an acceptable search speed, are proposed. The efficiency and correctness of the proposed algorithm were verified. The proposed algorithm and methods allow designing networks-on-chip with improved characteristics of diameter, average distance between nodes, edges count, and, as a result, reducing the area, occupied by network-on-chip, and other characteristics, in comparison with analogues based on other widespread regular topologies.
In this paper we consider games with preference relations. The main optimality concept for such games is concept of equilibrium. We introduce a notion of homomorphism for games with preference relations and study a problem concerning connections between equilibrium points of games which are in a homomorphic relation. The main result is finding covariantly and contravariantly complete families of homomorphisms.
The concept of the inclusion map of game with preference relations into a game with payoff functions is introduced. Necessary and sufficient conditions of the embeddability of game in factor-game are indicated. A necessary condition and also sufficient conditions for the existence of the inclusion of game with preference relations into a game with payoff functions are found.
A form for an unbiased estimate of the coefficient of determination of a linear regression model is obtained. It is calculated by using a sample from a multivariate normal distribution. This estimate is proposed as an alternative criterion for a choice of regression factors.
This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.