Geodesic
On maximal graphical partitions
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 112-124.

Voir la notice de l'article provenant de la source Math-Net.Ru

A partition of an integer $m$ is a sequence of nonnegative integers in nonincreasing order whose sum is equal to $m$. The length of a partition is the number of its nonzero parts. The set of all graphical partitions of $2m$, for a given $m$, is an order ideal of the lattice of all partitions of $2m$. We find new characterization of maximal graphical partitions and the number of maximal graphical partitions of length $n$. For each graphical partition $\lambda$ of integer $2m$ we construct maximal graphical partition $\mu$ of integer $2m$ with the same rank, which is dominate $\lambda$; also we find an algorithm that builds a sequence of elementary transformations from $\mu$ to $\lambda$.
Keywords: graph, lattice, graphical partition, Ferrer's diagram.
Mots-clés : integer partition 
@article{SEMR_2017_14_a3,
     author = {V. A. Baransky and T. A. Senchonok},
     title = {On maximal graphical partitions},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {112--124},
     publisher = {mathdoc},
     volume = {14},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2017_14_a3/}
}
TY  - JOUR
AU  - V. A. Baransky
AU  - T. A. Senchonok
TI  - On maximal graphical partitions
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2017
SP  - 112
EP  - 124
VL  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2017_14_a3/
LA  - ru
ID  - SEMR_2017_14_a3
ER  - 
%0 Journal Article
%A V. A. Baransky
%A T. A. Senchonok
%T On maximal graphical partitions
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2017
%P 112-124
%V 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2017_14_a3/
%G ru
%F SEMR_2017_14_a3
V. A. Baransky; T. A. Senchonok. On maximal graphical partitions. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 112-124. http://geodesic.mathdoc.fr/item/SEMR_2017_14_a3/

[1] M. O. Asanov, V. A. Baransky, V. V. Rasin, Discretnaya matematika: grafy, matroidy, algoritmy, Lan', Sankt-Peterburg, 2010

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

[3] T. Brylawski, “The lattice of integer partitions”, Discrete Mathematics, 6 (1973), 210–219 | MR

[4] Baransky V. A., Koroleva T. A., “Reshetka razbieniy naturalnogo chisla”, Doklady RAN, 418:4 (2008), 439–442 | Zbl

[5] Baransky V. A., Koroleva T. A., Senchonok T. A., “O reshetke razbieniy naturalnogo chisla”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 21, no. 3, 2015, 30–36 | MR | Zbl

[6] V. A. Baransky, T. A. Koroleva, T. A. Senchonok, “On the partition lattice of all integers”, Siberian Electronic Mathematical Reports, 13 (2016), 744–753

[7] V. A. Baransky, T. I. Nadymova, T. A. Senchonok, “A new algorithm generating graphical sequences”, Siberian Electronic Mathematical Reports, 13 (2016), 269–279 | Zbl

[8] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lekcii po teorii grafov, Nauka, M., 1990 | MR

[9] N. V. R. Mahadev, U. N. Peled, Threshold Graphs and Related Topics, Annals of Discrete Mathematics, Elsevier Science, 1995 | MR | Zbl

[10] A. Kohnert, “Dominance order and graphical partitions”, Electronic Journal of Combinatorics, 11:4 (2004), 1–17 | MR | Zbl

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