### AROUND THE ERDÖS–GALLAI CRITERION

#### Abstract

By an (integer) partition we mean a non-increasing sequence \(\lambda=(\lambda_1, \lambda_2, \dots)\) of non-negative integers that contains a finite number of non-zero components. A partition \(\lambda\) is said to be graphic if there exists a graph \(G\) such that \(\lambda = \mathrm{dpt}\,G\), where we denote by \(\mathrm{dpt}\,G\) the degree partition of \(G\) composed of the degrees of its vertices, taken in non-increasing order and added with zeros. In this paper, we propose to consider another criterion for a partition to be graphic, the ht-criterion, which, in essence, is a convenient and natural reformulation of the well-known Erdös–Gallai criterion for a sequence to be graphical. The ht-criterion fits well into the general study of lattices of integer partitions and is convenient for applications. The paper shows the equivalence of the Gale–Ryser criterion on the realizability of a pair of partitions by bipartite graphs, the ht-criterion and the Erdös–Gallai criterion. New proofs of the Gale–Ryser criterion and the Erdös–Gallai criterion are given. It is also proved that for any graphical partition there exists a realization that is obtained from some splitable graph in a natural way. A number of information of an overview nature is also given on the results previously obtained by the authors which are close in subject matter to those considered in this paper.

#### Keywords

#### Full Text:

PDF#### References

- Andrews G.E.
*The Theory of Partitions*. Cambridge: Cambridge University Press, 1984. 255 p. DOI: 10.1017/CBO9780511608650 - Baransky V.A., Koroleva T.A. The lattice of partitions of a positive integer.
*Doklady Math.*, 2008. Vol. 77, No. 1. P. 72–75. DOI: 10.1007/s11472-008-1018-z - Baransky V.A., Koroleva T.A., Senchonok T.A. On the partition lattice of an integer.
*Trudy Inst. Mat. i Mekh. UrO RAN*, 2015. Vol. 21, No. 3. P. 30–36. (in Russian) - Baransky V.A., Nadymova T.I., Senchonok T.A. A new algorithm generating graphical sequences.
*Sib. Electron. Mat. Izv.*, 2016. Vol. 13. P. 269–279. DOI: 10.17377/semi.2016.13.021 (in Russian) - Baransky V.A., Koroleva T.A., Senchonok T.A. On the partition lattice of all integers.
*Sib. Electron. Mat. Izv.*, 2016. Vol. 13. P. 744–753. DOI: 10.17377/semi.2016.13.060 (in Russian) - Baransky V.A., Senchonok T.A. On maximal graphical partitions.
*Sib. Electron. Mat. Izv.*, 2017. Vol. 14. P. 112–124. DOI: 10.17377/semi.2017.14.012 (in Russian) - Baransky V.A., Senchonok T.A. On threshold graphs and realizations of graphical partitions.
*Trudy Inst. Mat. i Mekh. UrO RAN*, 2017. Vol. 23, No. 2. P. 22–31. (in Russian) - Baransky V.A., Senchonok T.A. On the shortest sequences of elementary transformations in the partition lattice.
*Sib. Electron. Mat. Izv.*, 2018. Vol. 15. P. 844–852. DOI: 10.17377/semi.2018.15.072 (in Russian) - Baransky V.A., Senchonok T.A. On maximal graphical partitions that are the nearest to a given graphical partition.
*Sib. Electron. Mat. Izv.*, 2020. Vol. 17. P. 338–363. DOI: 10.33048/semi.2020.17.022 (in Russian) - Baransky V.A., Senchonok T.A. Bipartite threshold graphs.
*Trudy Inst. Mat. i Mekh.**UrO RAN*, 2020. Vol. 26, No. 2. P. 56–67. DOI: 10.21538/0134-4889-2020-26-2-56-67 (in Russian) - Baransky V.A., Senchonok T.A. An algorithm for taking a bipartite graph to the bipartite threshold form.
*Trudy Inst. Mat. i Mekh. UrO RAN*, 2022. Vol. 28, No. 4. P. 54–63. DOI: 10.21538/0134-4889-2022-28-4-54-63 (in Russian) - Baransky V.A., Senchonok T.A. Bipartite-threshold graphs and lifting rotations of edges in bipartite graphs.
*Trudy Inst. Mat. i Mekh. UrO RAN*, 2023. Vol. 29, No. 1. P. 24–35. DOI: 10.21538/0134-4889-2023-29-1-24-35 (in Russian) - Brylawski T. The lattice of integer partitions.
*Discrete Math.*, 1973. Vol. 6, No. 3. P. 201–219. DOI: 10.1016/0012-365X(73)90094-0 - Erdös P., Gallai T. Graphs with given degree of vertices.
*Mat. Lapok*, 1960. Vol. 11. P. 264–274. (in Hungarian) - Kohnert A. Dominance order and graphical partitions.
*Elec. J. Comb.*, 2004. Vol. 11, No. 1. Art. no. N4. P. 1–17. DOI: 10.37236/1845 - 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. - Sierksma G., Hoogeven H. Seven criteria for integer sequences being graphic.
*J. Graph Theory*, 1991. Vol. 15, No. 2. P. 223–231. DOI: 10.1002/jgt.3190150209

#### Article Metrics

### Refbacks

- There are currently no refbacks.