|
Conference publicationsAbstractsXV conferenceOn locally-balanced 2-partitions of some bipartite graphsShinararner 10/1, apt. 118, Yerevan, 0038, Armenia 2 pp.In this article undirected connected graphs without loops and multiple edges [1] are considered. The set of vertices of a graph G is denoted by V(G), the set of edges by E(G). The greatest degree of a vertex of a graph G is denoted by . For let’s set . 2-partition of a graph G is a function . 2-partition f of a graph G is locally-balanced1 iff for , (1) 2-partition f of a graph G is locally-balanced2 iff for . (2) The NP-completeness of the problem of existence of locally-balanced1 2-partition for bipartite graphs G with was proved in [2]. The NP-completeness of the problem of existence of locally-balanced2 2-partition for bipartite graphs G with was proved in [3]. The problems of existence and construction of 2-partitions described above are important since they correspond to the problems concerning distribution of influences of two opposite powers, which minimizes the probability of conflicts. The subjects of a simulated system may or may not have an ability of self-defence, thus during the modeling one should use the definitions (2) or (1) respectively. Let A be the set of graphs in which arbitrary two simple cycles [1] have at most one common vertex. Here, for bipartite graphs of A a necessary and sufficient condition for existence of locally-balanced1 2-partition is obtained.
|
