В. Е. Алексеев, Д. В. Захарова

ФГАОУ ВО «Национальный исследовательский Нижегородский государственный университет им. Н. И. Лобачевского» (г. Нижний Новгород, Российская Федерация)

Аннотация. В статье рассматриваются симметрические линейные пространства двудольных графов (СЛПДГ), т. е. множество двудольных графов с фиксированными долями, замкнутое относительно симметрической разности и перестановок вершин в каждой доле. В работе получено структурное описание всех СЛПДГ. Симметрические линейные пространства двудольных графов делят на тривиальные (четыре СЛПДГ) и нетривиальные. Нетривиальные, в свою очередь, подразделяют на два семейства: серия $C$, состоящая только из биполных графов (графов, являющихся дизъюнктным объединением двух полных двудольных графов (крылья графа)) и серия $D$, состоящая из множества графов, у которых степени вершин в~одной доле имеют одинаковую четность, а в другой могут быть любыми. Доказано, что любое СЛПДГ серии $D$ совпадает с одним из девяти множеств, заданных четностями степеней вершин. Для СЛПДГ серии $C$ (множество биполных графов) получено, что любое двустороннее СЛПДГ (т. е. содержащее графы, оба крыла которых имеют непустые доли) является пересечением множества всех биполных графов с множеством всех графов с четным числом ребер или каким-нибудь из пространств серии $D$.

Ключевые слова: граф, линейные пространства графов, двудольные графы, изоморфизм графов, симметрическая разность графов

Для цитирования: Алексеев В. Е., Захарова Д. В. О линейных пространствах двудольных графов // Журнал Средневолжского математического общества. 2024. Т. 26, № 1. С. 11–19. DOI: https://doi.org/10.15507/2079-6900.26.202401.11-19

Информация об авторах:

Алексеев Владимир Евгеньевич, доктор физико-математических наук, ORCID: https://orcid.org/0000-0003-1533-0697

Захарова Дарья Владимировна, старший преподаватель кафедры алгебры, геометрии и дискретной математики, ФГАОУ ВО «Национальный исследовательский Нижегородский государственный университет им. Н.,И. Лобачевского» (603022, Россия, г. Нижний Новгород, пр. Гагарина, д. 23), ORCID: https://orcid.org/0009-0008-8040-7164, darya.zakharova@itmm.unn.ru