Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Salii V. N. The ordered set of connected parts of a polygonal graph. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2013, vol. 13, iss. 2, pp. 44-51. DOI: 10.18500/1816-9791-2013-13-2-2-44-51, EDN: RHABJF

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 179)

The ordered set of connected parts of a polygonal graph

Salii Viacheslav Nikolaevich, Saratov State University

Under a polygonal graph is meant an oriented graph obtained from a cycle by some orientation of its edges. The set of all abstract (i.e. pairwise non-isomorphic) connected parts of a polygonal graph is ordered by graph embedding. Polygonal graphs are characterized for which this ordered set is a lattice. 

  1. Salii V. N. Minimal primitive extensions of oriented graphs. Prikladnaya diskretnaya matematika, 2008, no. 1(1), pp. 116–119 (in Russian).
  2. Trotter W. T., Moore J. I. Some theorems on graphs and posets. Discrete Math., 1976, vol. 15, no. 1, pp. 79– 84.
  3. Jacobson M. S., K´ezdy F. E., Seif S. The poset of connected induced subgraphs of a graph need not be Sperner. Order, 1995, vol. 12, no. 3, pp. 315–318.
  4. K´ezdy A. E., Seif S. When is a poset isomorphic to the poset of connected induced subgraphs of a graph? Southwest J. Pure Appl. Math., 1996, vol. 1, pp. 42– 50. Available at: http://rattler.cameron.edu/swjpam.html (Accessed 28, September, 2012).
  5. Nieminen J. The lattice of connected subgraphs of a connected graph. Comment. Math. Prace Mat., 1980, vol. 21, no. 1, pp. 187–193.
  6. Adams P., Eggleton R. B., MacDougall J. A. Degree sequences and poset structure of order 9 graphs. Proc. XXXV Southeast Conf. Comb., Graph Theory and Computing. Boca Raton, FL, USA, 2004, vol. 166, pp. 83– 95.
  7. Leach D., Walsh M. A characterization of latticeordered graphs. Proc. Integers Conf., 2005. New York, Gruyter, 2007, pp. 327–332. 8. Salii V. N. The system of abstract connected subgraphs of a linear graph. Prikladnaya diskretnaya matematika, 2012, no. 2(16), pp. 90–94 (in Russian).
Short text (in English):
(downloads: 59)