Trudy Instituta Matematiki i Mekhaniki UrO RAN
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2017, Volume 23, Number 2, Pages 22–31
DOI: https://doi.org/10.21538/0134-4889-2017-23-2-22-31
(Mi timm1409)
 

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
Full-text PDF (208 kB) Citations (2)
References:
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
Bibliographic databases:
Document Type: Article
UDC: 519.176
MSC: 05C07
Language: Russian
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
Citation in format AMSBIB
\Bibitem{BarSen17}
\by V.~A.~Baranskii, T.~A.~Senchonok
\paper On threshold graphs and realizations of graphical partitions
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2017
\vol 23
\issue 2
\pages 22--31
\mathnet{http://mi.mathnet.ru/timm1409}
\crossref{https://doi.org/10.21538/0134-4889-2017-23-2-22-31}
\elib{https://elibrary.ru/item.asp?id=29295247}
Linking options:
  • https://www.mathnet.ru/eng/timm1409
  • https://www.mathnet.ru/eng/timm/v23/i2/p22
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Trudy Instituta Matematiki i Mekhaniki UrO RAN
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025