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: 
25.05.2013
Full text:
download
(downloads: 171)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.17
DOI: 
10.18500/1816-9791-2013-13-2-2-44-51
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. 

Key words: 
polygonal graph
linear graph
binary vector
duality
ordered set
lattice
References: 
  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).
Received: 
13.11.2012
Accepted: 
23.04.2013
Published: 
31.05.2013
Short text (in English):
download
(downloads: 57)
  • 973 reads