Geodesic
On linear spaces of bipartite graphs
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 26 (2024) no. 1, pp. 11-19.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: graph, linear spaces of graphs, symmetric difference of graphs
Mots-clés : bipartite graph, graph isomorphism 
@article{SVMO_2024_26_1_a0,
     author = {V. E. Alekseev and D. V. Zakharova},
     title = {On linear spaces of bipartite graphs},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {11--19},
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2024_26_1_a0/}
}
TY  - JOUR
AU  - V. E. Alekseev
AU  - D. V. Zakharova
TI  - On linear spaces of bipartite graphs
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2024
SP  - 11
EP  - 19
VL  - 26
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2024_26_1_a0/
LA  - ru
ID  - SVMO_2024_26_1_a0
ER  - 
%0 Journal Article
%A V. E. Alekseev
%A D. V. Zakharova
%T On linear spaces of bipartite graphs
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2024
%P 11-19
%V 26
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2024_26_1_a0/
%G ru
%F SVMO_2024_26_1_a0
V. E. Alekseev; D. V. Zakharova. On linear spaces of bipartite graphs. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 26 (2024) no. 1, pp. 11-19. http://geodesic.mathdoc.fr/item/SVMO_2024_26_1_a0/

[1] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lektsii po teorii grafov, Nauka, M., 1990, 384 pp. | MR

[2] A. A. Zykov, Osnovy teorii grafov, Nauka, M., 1987, 383 pp.

[3] V. E. Alekseev, D. V. Zakharova, “O simmetricheskikh prostranstvakh grafov”, Diskretnyi analiz i issledovanie operatsii, 14:1 (2007), 24-26 | MR | Zbl

[4] D. V. Zakharova, “Simmetricheskie lineinye prostranstva grafov”, Diskretnaya matematika, 23:2 (2011), 104-107 | DOI

[5] V. E. Alekseev, V. A. Talanov, Grafy. Modeli vychislenii. Algoritmy, N. Novgorod Izd-vo Nizhegor. uni-ta im N.I.Lobachevskogo, 2005, 308 pp.

[6] V. E. Alekseev, V. A. Talanov, Grafy i algoritmy. Struktury dannykh.Modeli vychislenii., M. INTUIT, 2006, 319 pp.

[7] V. E. Alekseev, D. V. Zakharova, Teoriya grafov, N. Novgorod Izd-vo Nizhegor. uni-ta im N.I.Lobachevskogo, 2018, 118 pp.

[8] V. E. Alekseev, Issledovanie kolichestvennykh i slozhnostnykh kharakteristik nasledstvennykh klassov grafov, na soisk. d-ra fiz.-mat. nauk, N. Novgorod, 2002, 113 pp.