Bipartite threshold graphs

V. A. Baranskii ; T. A. Senchonok

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 2, pp. 56-67

Résumé

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.

Détail

Mots-clés : integer partition, bipartite graph
Keywords: threshold graph, Ferrer's 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] Ivanyi A., Lucz L., Gombos G., Matuszka T., “Parallel enumeration of degree sequences of simple graphs”, Acta Univ. Sapientiae, Informatica, 4:2 (2012), 260–288 | MR | Zbl

[4] Tripathi A., Venugopalan S., West D.B., “A short constructive proof of the Erdos–Gallai characterization of graphic lists”, Discrete Math., 310:4 (2010), 833–834 | DOI | MR

[5] Bisi C., Ciaselotti G., Oliverio P.A., “A natural extension of the Young partition lattice”, Advances in Geometry, 15:3 (2015), 263–280 | DOI | MR | Zbl

[6] Baransky V.A., Koroleva T.A., “The lattice of partitions of a positive integer”, Dokl. Math., 77:1 (2008), 72–75 | DOI | MR | Zbl

[7] Baransky V.A., Koroleva T.A., Senchonok T.A., “On the partition lattice of all integers”, Sib. Elect. Math. Reports, 13 (2016), 744–753 | DOI | MR | Zbl

[8] Kohnert A., “Dominance order and graphical partitions”, Elec. J. Comb., 11:4 (2004), 1–17 | DOI | MR | Zbl

[9] Erdös P., Gallai T., “Graphs with given degree of vertices”, Math. Lapok, 11 (1960), 264–274

[10] Baransky V.A., Senchonok T.A., “On maximal graphical partitions that a the nearest to a given graphical partition”, Sib. Elect. Math. Reports, 17 (2020), 338–363 | DOI | MR

[11] 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

[12] Baransky V.A., Senchonok T.A., “On the shortest sequences of elementary transformations in the partition lattice”, Sib. Elect. Math. Reports, 15 (2018), 844–852 | DOI | MR