RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2017 Volume 23, Number 2, Pages 22–31 (Mi timm1409)

This article is cited in 2 papers

On threshold graphs and realizations of graphical partitions

V. A. Baranskii, T. A. Senchonok

Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg

Abstract: 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, integer partition, graphical partition, Ferrers diagram.

UDC: 519.176

MSC: 05C07

Received: 20.10.2016

DOI: 10.21538/0134-4889-2017-23-2-22-31



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025