Microsoft Word - I. Karapetyan_12+.doc


Mathematical Problems of Computer Science 34, 2010. 

35 

 

 

 

On some Problems in Graph Theory 
Iskandar  A. Karapetyan 

Institute for Informatics and Automation Problems 
 

Some existence problems are studied related to cycles and paths with given properties, and 
some algorithms are found solving these problems. In particular, the existence problems are 
studied concerning hamiltonian graphs, pancyclic directed and vertex pancyclic directed graphs. 
It is proved that in any directed graph G of order p (p ≥13) with semidegrees at least (p-3)/2 
every vertex belongs to a cycle of length k, k [9, p-1], for each integer k, and if p≥30 then this 
vertex belongs to  cycles of lengths 6,7,8. As a corollary, one can find a cycle with given length 
and passing through given vertex by a polynomial time algorithm. 

A number of upper bounds are obtained for transversal and chromatic numbers for 
intersection graphs of families of rectangles with sides parallel to coordinate axes in the plane. 

Some effective algorithms are given for one-layer and single-row problem, as well as for 
VLSI global routing problem. 

It is proved that each 3-connected graph G with (n+2k)/4 has a dominating cycle, and each 
4-connected graph G either has a cycle of length at least 4-2k or has a dominating cycle, where 
n denotes the order,  the minimum degree and k the connectivity of G. 

Some problems are studied by graph theorists under heading of R.Kamalyan, concerning 
interval edge colorings, generalized interval edge colorings, interval total colorings, cyclic-
continued edge colorings and local-balanced vertex partitions. 

It is proved the existence of cyclic-continued edge coloring for each tree and all possible 
values of a number of colors in such colorings are found. 

Some problems are studied concerning the existence (as well as constructing and estimating 
of some parameters) of interval edge colorings for bipartite graphs, cylinders and tores, complete 
graphs and n-cubes, complete bipartite and some regular graphs. The idea of interval edge 
colorings is generalized. А particular case of a problem (Erdos, 1991) concerning bipartite 
graphs without interval edge colorings is solved. 

 

References 

1. С.Х. Дарбинян и  И.А. Карапетян, О вершинной панцикличности направленных 
графов с большими полустепенями. Мат. воп. киб. и выч. тех.,  №29,  с. 66-84, 2007.  

2. S.Kh. Darbinyan and I.A. Karapetyan, A note on short paths in oriented graphs, 
Mathematical Problems of Computer Sciences 33 (2010) 35-40. 

3. И.А. Карапетян и С.Х. Дарбинян,  Однарядная трассировка. CSIT Conference,  
September 2007, Yerevan, Armenia. 

4.  И.А. Карапетян и С.Х. Дарбинян, О двух задачах трассировки,  Computer Sciense 
and Information Technologies,  28 September – 2 October, p. 439-442, 2009, Yerevan, 
Armenia. 



36                

5. Zh.G. Nikoghosyan, Dirac-type generalizations concerning large cycles in graphs, 
Discrete Mathematics 309 (2009) 1925-1930. 

6. M.Zh. Nikoghosyan, Zh.G. Nikoghosyan, Large cycles in 4-connected graphs, Discrete 
Mathematics 311, no.4 (2011) 302-306. 

7. R.R. Kamalian, V.V. Mkrtchyan, On special maximum matchings constructing, Discrete        
Mathematics 308, 2008, pp 1792-1800.  

8. R.R. Kamalian, On a number of colors in cyclically interval edge colorings of trees, 
LiTH-MAT-R-2010/09-SE, Linkoping University, 2010.  

9. P.A. Petrosyan, Interval edge-colorings of complete graphs and n dimensional cubes, 
Discrete Mathematics 310, 2010, pp. 1580-1587. 

10. P.A. Petrosyan, H.Z. Arakelyan, V.M. Baghdasaryan, A  generalization of interval edge-
colorings of graphs, Discrete Applied Mathematics 158, 2010, pp. 1827-1837.