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:
25.05.2013
Full text:
(downloads: 193)
Language:
Russian
Heading:
UDC:
519.17
EDN:
RHABJF
The ordered set of connected parts of a polygonal graph
Autors:
Salii Viacheslav Nikolaevich, Saratov State University
Abstract:
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.
References:
- Salii V. N. Minimal primitive extensions of oriented graphs. Prikladnaya diskretnaya matematika, 2008, no. 1(1), pp. 116–119 (in Russian).
- Trotter W. T., Moore J. I. Some theorems on graphs and posets. Discrete Math., 1976, vol. 15, no. 1, pp. 79– 84.
- 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.
- 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).
- Nieminen J. The lattice of connected subgraphs of a connected graph. Comment. Math. Prace Mat., 1980, vol. 21, no. 1, pp. 187–193.
- 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.
- 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).
Received:
13.11.2012
Accepted:
23.04.2013
Published:
31.05.2013
Short text (in English):
(downloads: 78)
- 1136 reads