НАН РА. Математические вопросы кибернетики и вычислительной техники=Mathematical problems of computer science

On Locally-Balanced 2-Partitions of Complete Multipartite Graphs

Gharibyan, Aram H. and Petrosyan, Petros A. (2018) On Locally-Balanced 2-Partitions of Complete Multipartite Graphs. Математические вопросы кибернетики и вычислительной техники, № 49. pp. 7-17. ISSN 0131-4645

[img] PDF
Download (338Kb)

    Abstract

    A 2-partition of a graph G is a function f : V (G) ! fWhite;Blackg. A 2-partition f of a graph G is locally-balanced with an open neighborhood if for every v € V (G), ││{u € NG(v): f(u) =Whitegj}│-│{u € NG(v): f(u) = Black}││≤ 1, where NG(v) = fu 2 V (G): uv 2 E(G)g. A 2-partition f0 of a graph G is locallybalanced with a closed neighborhood if for every v € V(G), ││{u € NG[v]: f0(u) =White}│-│{u € NG[v]: f(u) = Black}││ ≤ 1, where NG[v] = NG(v) u [v}. In this paper we give necessary and su±cient conditions for the existence of locally-balanced 2-partitions of complete multipartite graphs.

    Item Type: Article
    Additional Information: Լրիվ բազմակողմանի գրաֆների լոկալ-հավասարակշռված 2-տրոհումների մասին / Ա. Ղարիբյան, Պ. Պետրոսյան: О локально-сбалансированных 2-разбиениях полных многодольных графов / А. Гарибян, П. Петросян
    Uncontrolled Keywords: 2-partition, Locally-balanced 2-partition, Equitable coloring, Complete multipartite graph.
    Subjects: Q Science > QA Mathematics > Graph theory
    Divisions: UNSPECIFIED
    Depositing User: FSL Bibl. Dept.
    Date Deposited: 22 Oct 2018 12:10
    Last Modified: 22 Oct 2018 12:10
    URI: http://compsci.asj-oa.am/id/eprint/895

    Actions (login required)

    View Item