Bipartite-threshold graphs and lifting rotations of edges in bipartite graphs

V. A. Baranskii ; T. A. Senchonok

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 1, pp. 24-35

Résumé

A bipartite graph $H=(V_1,E,V_2)$ is called a bipartite-threshold graph if it has no lifting triples $(x,v,y)$ such that $x,y\in V_1$, $v\in V_2$ or $x,y\in V_2$, $v\in V_1$. Every bipartite graph $H=(V_1,E,V_2)$ can be transformed to a bipartite-threshold graph by a finite sequence of such bipartite lifting rotations of edges. In our previous paper, we studied the properties of bipartite-threshold graphs and noted their importance for the class of threshold graphs. Now we want to show the importance of these graphs for the class of bipartite graphs. We will always understand an integer partition as a nonincreasing sequence of nonnegative integers that contains only finitely many nonzero terms. For any integer partitions $\alpha$ and $\beta$ such that $\mathrm{sum}(\alpha)=\mathrm{sum}(\beta)$ and $\alpha\leq\beta^*$, where $\beta^*$ is the conjugate partition of $\beta$, we denote by $\mathrm{BG}(\alpha, \beta)$ the family of bipartite graphs $H=(V_1,E,V_2)$ implementing the pair of partitions $(\alpha, \beta)$, i.e., the family of all bipartite graphs for which the given pair of partitions is composed of the degrees of vertices in the first and second parts of the graph, respectively, supplemented with zeros. In this paper we describe the bipartite-threshold graphs from the family $\mathrm{BTG}_\uparrow(\alpha, \beta)$ of all bipartite-threshold graphs that can be obtained from the graphs of the family $\mathrm{BG}(\alpha, \beta)$ by bipartite lifting rotations of edges. We also find the smallest length of sequences of bipartite lifting rotations of edges transforming graphs from $\mathrm{BG}(\alpha,\beta)$ to graphs belonging to $\mathrm{BTG}_\uparrow(\alpha, \beta)$, give an algorithm that finds a bipartite-threshold graph from $\mathrm{BG}(\alpha, \beta)$, and describe a procedure that generates all graphs in a family $\mathrm{BG}(\alpha, \beta)$ from one graph of this family.

Détail

Mots-clés : integer partition, bipartite graph
Keywords: threshold graph, bipartite-threshold graph, Ferrers diagram.

Bibliographie

[1] Asanov M.O., Baranskii V.A., Rasin V.V., Diskretnaya matematika: grafy, matroidy, algoritmy, 2-e izd., ispr. i dop., Lan, SPb., 2010, 368 pp.

[2] Andrews G.E., The theory of partitions, Cambridge University Press, Cambridge, 1976, 255 pp. | MR

[3] Mahadev N.V.R., Peled U.N., Threshold graphs and related topics, Ser. Annals of Discr. Math., 56, North-Holland Publishing Co., Amsterdam, 1995, 542 pp. | MR

[4] Baranskii V.A., Koroleva T.A., Senchonok T.A., “O reshetke razbienii vsekh naturalnykh chisel”, Sib. elektron. mat. izv., 13 (2016), 744–753 | DOI | MR | Zbl

[5] Baranskii V.A., Senchonok T.A., “O kratchaishikh posledovatelnostyakh elementarnykh preobrazovanii v reshetke razbienii naturalnykh chisel”, Sib. elektron. mat. izv., 15 (2018), 844–852 | DOI | Zbl

[6] Havel V., “A remark on the existence of finite graphs (in Czech)”, Câsopic Pêst. Mat., 80:4 (1955), 477–481 | MR