V.A. Baransky, T.A. Senchonok. Bipartite threshold graphs ... P. 56-67

A triple of distinct  vertices $(x,v,y)$ in a graph $G=(V,E)$ such that $xv\in E$ and $vy\notin E$ is called lifting if $\mathrm{deg}(x)\leq \mathrm{deg}(y)$ and lowering if $\mathrm{deg}(x)\geq 2+\mathrm{deg}(y)$. A transformation $\varphi$ of a graph $G$ that replaces $G$ with $\varphi(G)=G-xv+vy$ is called an edge rotation corresponding to a triple of vertices $(x,v,y)$. For a lifting (lowering) triple $(x,v,y)$, the corresponding edge rotation is called lifting (lowering). An edge rotation in a graph $G$ is lifting if and only if its inverse in the graph $\varphi(G)$ is lowering. A bipartite graph $H=(V_1,E,V_2)$ is called a  bipartite threshold graph if it has no lifting triples such that $x,y\in V_1$ and $v\in V_2$ or $x, y\in V_2$ and $v\in V_1$. The aim of paper is to give some characteristic properties of bipartite threshold graphs. In particular, every such graph $(V_1,E,V_2)$ is embedded in the threshold graph $(K(V_1),E,V_2)$, where $K(V_1)$ is the complete graph on the vertex set $V_1$. Note that a graph is a threshold graph if and only if it has no lifting triples of vertices. Every bipartite graph can be obtained from a bipartite threshold graph by means of lowering edge rotations. Using the obtained results and Kohnert's criterion for a partition to be graphical, we give a new simple proof of the well-known Gale-Ryser theorem on the representation of two partitions by degree partitions of the parts in a bipartite graph.

Keywords: integer partition, threshold graph, bipartite graph, Ferrer's diagram

Received March 15, 2019

Revised May 8, 2020

Accepted May 18, 2020

Vitaly Anatol’evich Baransky, Dr. Phys.-Math. Sci., Prof., Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: vitaly.baransky@urfu.ru

Tatiana Aleksandrovna Senchonok, Cand. Phys.-Math. Sci., Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: tatiana.senchonok@urfu.ru

REFERENCES

1.   Asanov M.O., Baransky V.A., Rasin V.V. Diskretnaya matematika: grafy, matroidy, algoritmy [Discrete Mathematics: graphs, matroids, algorithms]. SPb: Lan’, 2010, 368 p. ISBN: 978-5-8114-1068-2 .

2.   Andrews G.E. The theory of partitions. Cambridge: Cambridge University Press, 1976, 255 p. ISBN: 9781107093683 .

3.   Ivanyi A., Lucz L., Gombos G., Matuszka T. Parallel enumeration of degree sequences of simple graphs. Acta Univ. Sapientiae, Informatica, 2012, vol. 4, no. 2, pp. 260–288.

4.   Tripathi A., Venugopalan S., West D.B. A short constructive proof of the Erdos–Gallai characterization of graphic lists. Discrete Mathematics, 2010, vol. 310, no. 4, pp. 843–844. doi: 10.1016/j.disc.2009.09.023 

5.   Bisi C., Ciaselotti G., Oliverio P.A. A natural extension of the Young partition lattice. Advances in Geometry, 2015, vol. 15, no. 3, pp. 263–280. doi: 10.1515/advgeom-2015-0017 

6.   Baransky V.A., Koroleva T.A. The lattice of partitions of a positive integer. Doklady Math., 2008, vol. 77, no. 1, pp. 72–75. doi: 10.1007/s11472-008-1018-z 

7.   Baransky V.A., Koroleva T.A., Senchonok T.A. On the partition lattice of all integers. Sib. Elect. Math. Reports, 2016, vol. 13, pp. 744–753. doi: 10.17377/semi.2016.13.060 

8.   Kohnert A. Dominance order and graphical partitions. Elec. J. Comb., 2004, vol. 11, no. 4, pp. 1–17. doi: 10.37236/1845 

9.   Erdos P., Gallai T. Graphs with given degree of vertices. Math. Lapok, 1960, vol. 11, no. 4, pp. 264–274 (in Hungarian).

10.   Baransky V.A., Senchonok T.A. On maximal graphical partitions that are the nearest to a given graphical partition. Sib. Elect. Math. Reports, 2020, vol. 17, pp. 338–363.
doi 10.33048/semi.2020.17.022 

11.   Mahadev N.V.R., Peled U.N. Threshold Graphs and Related Topics. Ser. Annals of Discr. Math., vol. 56, Amsterdam: North-Holland Publishing Co., 1995, 542 p. doi: 10.1016/s0167-5060(13)71063-x 

12.   Baransky V.A., Senchonok T.A. On the shortest sequences of elementary transformations in the partition lattice. Sib. Elect. Math. Reports, 2018, vol. 15, pp. 844–852 (in Russian). doi 10.17377/semi.2018.15.072 

Cite this article as: V.A.Baransky, T.A.Senchonok. Bipartite threshold graphs. Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 2, pp. 56-67.