Geodesic
On threshold graphs and realizations of graphical partitions
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 2, pp. 22-31
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A triple of 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)\geq2+\mathrm{deg}(y)$. A lowering rotation of an edge in a graph $G$ corresponding to a lowering triple $(x,v,y)$ is a transformation of this graph that replaces the edge $xv$ by the edge $vy$. We prove that $G$ is a threshold graph if and only if it has no lifting triples of vertices. This result has three corollaries: The graphical partition corresponding to $G$ is a maximal graphical partition if and only if $G$ is a threshold graph. An arbitrary partition $\lambda$ is a maximal graphical partition if and only if the head of $\lambda$ is equal to its tail. Each realization of an arbitrary graphical partition $\mu$ can be obtained by a finite sequence of lowering rotations of edges from a threshold realization of an appropriate maximal graphical partition $\lambda$ such that $\lambda\geq\mu$.
Keywords: graph, threshold graph, lattice, graphical partition, Ferrers diagram.
Mots-clés : integer partition 
@article{TIMM_2017_23_2_a2,
     author = {V. A. Baranskii and T. A. Senchonok},
     title = {On threshold graphs and realizations of graphical partitions},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {22--31},
     year = {2017},
     volume = {23},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2017_23_2_a2/}
}
TY  - JOUR
AU  - V. A. Baranskii
AU  - T. A. Senchonok
TI  - On threshold graphs and realizations of graphical partitions
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2017
SP  - 22
EP  - 31
VL  - 23
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2017_23_2_a2/
LA  - ru
ID  - TIMM_2017_23_2_a2
ER  - 
%0 Journal Article
%A V. A. Baranskii
%A T. A. Senchonok
%T On threshold graphs and realizations of graphical partitions
%J Trudy Instituta matematiki i mehaniki
%D 2017
%P 22-31
%V 23
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2017_23_2_a2/
%G ru
%F TIMM_2017_23_2_a2
V. A. Baranskii; T. A. Senchonok. On threshold graphs and realizations of graphical partitions. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 2, pp. 22-31. http://geodesic.mathdoc.fr/item/TIMM_2017_23_2_a2/

[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] Brylawski T., “The lattice of integer partitions”, Discrete Math., 6 (1973), 201–219 | DOI | MR | Zbl

[4] Baransky V.A., Senchonok T.A., “On maximal graphical partitions”, Sib. Elect. Math. Reports, 14 (2017), 112–124 | DOI | Zbl

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

[6] Baranskii V.A., Koroleva T.A., Senchonok T.A., “O reshetke razbienii naturalnogo chisla”, Tr. In-ta matematiki i mekhaniki UrO RAN, 21:3 (2015), 30–36 | MR

[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

[8] Baransky V.A., Nadymova T.I., Senchonok T.A., “A new algorithm generating graphical sequences”, Sib. Elect. Math. Reports, 13 (2016), 269–279 | DOI | MR | Zbl

[9] Mahadev N.V.R., Peled U.N., Threshold graphs and related topics, Annals of Discr. Math., 56, North-Holland Publishing Co., Amsterdam, 1995, 542 p pp. | MR