Title:

Լրիվ բազմակողմանի գրաֆների լոկալ հավասարակշռված 2-տրոհումների մասին ; О локально-сбалансированных 2-разбиенияхполных многодольных графов

Author:

Ղարիբյան Արամ ; Гарибян Арам

Type:

Հոդված

Co-author(s) :

Պետրոսյան Պետրոս ; Петросян Петрос

Abstract:

f : V(G) - {White, Black} ֆունկցիան կոչվում է G գրաֆի 2-տրոհում: G գրաֆի f 2-տրոհումը կոչվում է լոկալ-հավասարակշռված 2-տրոհում բաց շրջակայքով, եթե կամայական v  V(G) գագաթի համար տեղի ունի \\{u  NG(v): f (u) = White}|-|{u  NG(v): f (u) = Black}||  1, որտեղ Ng(v) = {u V(G): uv  E (G)}: G գրաֆի f ՚ 2-տրոհումը կոչվում է լոկալ հավասարակշռված տրոհում փակ շրջակայքով, եթե կամայական v  V (G) գագաթի համար տեղի ունի \\{u  NG[v]: f (u) = White}| ֊- |{u 2 NG[v]: f (u) = Black}||  1, որտեղ NG[v] = NG(v) U {v}: Այս աշխատանքում տրվում են լրիվ բազմակողմանի գրաֆների լոկալ-հավասարակշռված տրոհումների գոյության անհրաժեշտ և բավարար պայմաններ:
; 2-разбиением графа G называется функция f : V(G) - {White, Black}. 2-разбиение f графа G называется локально-сбалансированным с открытой окрестностью, если для любой вершины v  V (G) ||{и е NG(v): f (и) = White}| — {u  NG(v): f (и) = Black}|| < 1, где Ng(v) = {и  V(G): uv  E (G)}. 2-разбиение f графа G называется локальносбалансированным с закрытой окрестностью, если для любой вершины v  V (G) ||{u  NG[v]: f (и) = White}| — |{u  NG[v]: f (и) = Black}|| < 1, где NG[v] = Ng(v) U {v}. В настоящей работе даются необходимые и достаточные условия существования локально-сбалансированных 2-разбиений полных многодольных графов.

Publisher:

ՀՀ ԳԱԱ «ԳԻՏՈՒԹՅՈՒՆ» ՀՐԱՏԱՐԱԿՉՈՒԹՅՈՒՆ ; Издательство "Гитутюн" НАН РА

Language:

Անգլերեն ; Английский

Journal or Publication Title:

Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր ; Математические вопросы кибернетики и вычислительной техники

Affiliation:

Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ ; Երևանի պետական համալսարան ; Институт проблем информатики и автоматизации ; Ереванский Государственный Университет

Country:

Հայաստան ; Армения