Regular subgraphs of linear extension graphs

Author O. S. Bondarenko
buenasdiaz@gmail.com
Zaporizhzhya National University

Abstract The paper deals with the properties of regular subgraphs of linear extension graphs. We obtain a necessary and sufficient condition for regularity of linear extension graphs, prove a pro- position on cardinality and degree partition of special linear extension graphs boundaries, give a characterization of a linear extension graphs class with 0 or 1 bump numbers linear extensions.
Keywords graph; regularity; linear extension
Reference 1. West D.B. Generating linear extensions by adjacent transpositions// Douglas BrentWest, J. Comb. Theory Ser. B. – 1993. – V.58. – ¹1. – P. 58–64.

2. Naatz M. The graph of linear extensions revisited// SIAM J. Disc. Math. – 2000. – V.13. – ¹3. – P. 354– 369.

3. Felsner S., Massow M. Linear Extension Diameter of Downset Lattices of 2-Dimensional Posets// Electronic Notes in Discrete Mathematics. – 2009. – V.34, ¹1. – P. 313–317.

4. Naatz M. Acyclic Orientations of Mixed Graphs, Thesis. – Berlin, 2001. – 125 p.

5. Trotter W.T., Graham R.L., Gr.otschel M., Lov.asz L., Partially ordered sets, in: Handbook of Combinatorics, Elsevier, Amsterdam, 1995, p. 433–480.

6. Keller M.T. Some Results on Linear Discrepancy for Partially Ordered Sets. Thesis. – Atlanta, 2010. – 69 p.

7. Habib M., M.ohring R.H., Steiner G. Computing the Bump Number is Easy// Order. – 1988. – V.5. – P. 107–129.

8. Jung H.C. Lower bounds of the number of jump optimal linear extensions: Products of some posets// Bull. Korean Math. Soc. – 1995. – V.32. – ¹2. – P. 171–177.

9. Knuth D.E. Two notes on notation// American Math. Monthly. – 1992. – V.99. – ¹5. – P. 403–422.

Pages 6-11
Volume 36
Issue 1
Year 2011
Journal Matematychni Studii
Full text of paper PDF
Table of content of issue HTML