# 71655

## Автор(ов):

5

Параметры публикации

Тезисы доклада

## Название:

Majority domination problem for graphs with given maximum vertex degree

## ISBN/ISSN:

978-5-907366-77-0

## Наименование конференции:

• 14th International Conference "Intelligent Data Processing" (Moscow, 2022)

## Наименование источника:

• Book of abstract of the 14th International Conference "Intelligent Data Processing" (Moscow, 2022)

• Moscow

## Издательство:

• Russian Academy of Sciences

2022

## Страницы:

433-436
Аннотация
A simplified model of democratic voting in society was considered. Society consists of people combined in a social graph. Two people are connected by an edge if they communicate with each other. Each person initially has his or her own intention about voting: will he or she vote "for" or "against". However, people tend to pay attention to the opinions of those around them with whom they interact. A person tends to vote the way most of his acquaintances think, even if their prevailing opinion does not coincide with his opinion. Of interest are such distributions of opinions on graphs in which voting is successful, but the number of people who initially intend to vote "for" is minimal (so called positive vertices). Such cases are referred to here as optimal cases. For arbitrary graphs, the optimal case is achieved with only two positive vertices to which all other vertices are connected. This is interpreted as the fact that democratic voting does not decide in favor of the majority in the general case. However, such an optimal social graph is rarely found in general practice case. In practice, a social graph consists of a large number of vertices with a relatively small degree in each. Then we considered the graphs with the restriction on the vertex degree from above. An empirical formula expressing the optimal value of positive vertices was obtained, and the graph on which the optimal case is reached was also obtained. It turns out that the more the vertex degree constraint from above, the less the optimal number of positive vertices. The difference between the optimal number of positive vertices in regular graphs and almost regular graphs in which the degree of a vertex can take two adjacent values is also considered. Numerical experiments have shown that the optimal value of positive vertices in both graphs with the same number of vertices and close constraints on the degree of a vertex coincides in all cases except two exceptions of special kind.

## Библиографическая ссылка:

Лемтюжникова Д.В., Чеботарев П.Ю., Губко М.В., Кудинов И.Д., Шушко Н.И. Majority domination problem for graphs with given maximum vertex degree / Book of abstract of the 14th International Conference "Intelligent Data Processing" (Moscow, 2022). Moscow: Russian Academy of Sciences, 2022. С. 433-436.

Да