AROUND THE ERDÖS–GALLAI CRITERION
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
AROUND THE ERDÖS–GALLAI CRITERION
|
|
| Автор |
Baransky, V. A.
Senchonok, T. A. |
|
| Тематика |
BIPARTITE GRAPH
BIPARTITE-THRESHOLD GRAPH FERRERS DIAGRAM INTEGER PARTITION THRESHOLD GRAPH |
|
| Описание |
By an (integer) partition we mean a non-increasing sequence λ = (λ1,λ2,…) of non-negative integers that contains a finite number of non-zero components. A partition λ is said to be graphic if there exists a graph G such that λ = dptG, where we denote by dptG 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. © 2023, Krasovskii Institute of Mathematics and Mechanics. All rights reserved.
|
|
| Дата |
2024-04-05T16:30:40Z
2024-04-05T16:30:40Z 2023 |
|
| Тип |
Article
Journal article (info:eu-repo/semantics/article) |info:eu-repo/semantics/publishedVersion |
|
| Идентификатор |
Baransky, V & Senchonok, T 2023, 'AROUND THE ERDÖS–GALLAI CRITERION', Ural Mathematical Journal, Том. 9, № 1, стр. 29-48. https://doi.org/10.15826/umj.2023.1.003
Baransky, V., & Senchonok, T. (2023). AROUND THE ERDÖS–GALLAI CRITERION. Ural Mathematical Journal, 9(1), 29-48. https://doi.org/10.15826/umj.2023.1.003 2414-3952 Final All Open Access, Gold https://www.scopus.com/inward/record.uri?eid=2-s2.0-85166942630&doi=10.15826%2fumj.2023.1.003&partnerID=40&md5=723b0ac3f4c9318b61b96157e8662124 https://umjuran.ru/index.php/umj/article/download/640/pdf http://elar.urfu.ru/handle/10995/130700 54265303 10.15826/umj.2023.1.003 85166942630 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
cc-by https://creativecommons.org/licenses/by/4.0/ |
|
| Формат |
application/pdf
|
|
| Издатель |
Krasovskii Institute of Mathematics and Mechanics
|
|
| Источник |
Ural Mathematical Journal
Ural Mathematical Journal |
|