V. E. Alekseev, D. V. Zakharova

National Research Lobachevsky State University of Nizhny Novgorod (Nizhny Novgorod, Russian Federation)

Abstract. The article considers symmetric linear spaces of bipartite graphs (SLSBG), i.e. the set of bipartite graphs with fixed lobes closed with respect to the symmetric difference and permutations of vertices in each lobe. The operation of symmetric difference itself is introduced in this work. The paper provides a structural description of all SLSBG. Symmetric linear spaces of bipartite graphs are divided into trivial (four SLSBG) and nontrivial. Non-trivial ones, in turn, are divided into two families. The first is $C$-series consisting only of bicomplete graphs, i.e. graphs that are a disjunct union of two complete bipartite graphs graph wings). The second family is $D$-series that includes graphs in which the degrees of vertices in one lobe have the same parity, and in the other lobe these degrees may be arbitrary. It is proved that every SLSBG of the $D$-series coincides with one of nine sets defined by the parity of the vertices’ degrees. For the SLSBG of the $C$-series it is obtained that every two-sided SLSBG (i.e., containing graphs whose both wings have nonempty lobes) is the intersection of the set of all bicomplete graphs with the set of all graphs with an even number of edges or with any space of the $D$-series.

Key Words: graph, linear spaces of graphs, bipartite graph, graph isomorphism, symmetric difference of graphs

For citation: V. E. Alekseev, D. V. Zakharova. On linear spaces of bipartite graphs. Zhurnal Srednevolzhskogo matematicheskogo obshchestva. 26:1(2024), 11–19. DOI: https://doi.org/10.15507/2079-6900.26.202401.11-19

Information about the authors:

Vladimir E. Alekseev, D.Sci. (Phys.-Math.), ORCID: https://orcid.org/0000-0003-1533-0697

Darya V. Zakharova, Senior Lecturer, Department of Algebra, Geometry and Discrete Mathematics, National Research Lobachevsky State University of Nizhny Novgorod (23 Gagarina Av., Nizhny Novgorod 603022, Russia), ORCID: https://orcid.org/0009-0008-8040-7164, darya.zakharova@itmm.unn.ru