|
This article is cited in 2 scientific papers (total 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.
Received: 20.10.2016
Citation:
V. A. Baranskii, T. A. Senchonok, “On threshold graphs and realizations of graphical partitions”, Trudy Inst. Mat. i Mekh. UrO RAN, 23, no. 2, 2017, 22–31
Linking options:
https://www.mathnet.ru/eng/timm1409 https://www.mathnet.ru/eng/timm/v23/i2/p22
|
|