Cite this article as:
Salii V. N. The ordered set of connected parts of a polygonal graph. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2013, vol. 13, iss. 2, pp. 44-51. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-2-44-51
The ordered set of connected parts of a polygonal graph
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.
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).
