|
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∈E and vy∉E is called lifting if deg(x)≤deg(y) and lowering if deg(x)≥2+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 λ is a maximal graphical partition if and only if the head of λ is equal to its tail. Each realization of an arbitrary graphical partition μ can be obtained by a finite sequence of lowering rotations of edges from a threshold realization of an appropriate maximal graphical partition λ such that λ≥μ.
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
|
Statistics & downloads: |
Abstract page: | 328 | Full-text PDF : | 97 | References: | 57 | First page: | 13 |
|