| 1. |
- Asratian, Armen S., 1951-, et al.
(författare)
-
A characterization of panconnected graphs satisfying a local ore-type condition
- 1996
-
Ingår i: Journal of Graph Theory. - : Wiley Subscription Services, Inc., A Wiley Company. - 0364-9024 .- 1097-0118. ; 22:2, s. 95-103
-
Tidskriftsartikel (refereegranskat)abstract
- It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η 3,4) there is a cycle of length k containing xy.Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle.Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc.
|
|
| 2. |
- Asratian, Armen S., et al.
(författare)
-
New class of 0-1 integer programs with tight approximation via linear relaxations
- 2001
-
Ingår i: Mathematical Methods of Operations Research. - : Springer. - 1432-2994 .- 1432-5217. ; 53:3, s. 363-370
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of estimating optima of integer programs { max cx | Axhb,0hxh1, x m integral} where b>0, cS0 are rational vectors and A is an arbitrary rational m 2n matrix. Using randomized rounding we find an efficiently verifiable sufficient condition for optima of such integer programs to be close to the optima q of their linear relaxations. We show that our condition guarantees that for any constant )>0 and sufficiently large n there exists a feasible integral solution z such that qS czS(1m))q.
|
|
| 3. |
- Asratian, Armen S., 1951-, et al.
(författare)
-
On graphs satisfying a local ore-type condition
- 1996
-
Ingår i: Journal of Graph Theory. - : Wiley Subscription Services, Inc., A Wiley Company. - 0364-9024 .- 1097-0118. ; 21:1, s. 1-10
-
Tidskriftsartikel (refereegranskat)abstract
- {For an integer i, a graph is called an Li-graph if, for each triple of vertices u, v, w with d(u, v) = 2 and w (element of) N(u) (intersection) N(v), d(u) + d(v) ≥ | N(u) (union) N(v) (union) N(w)| —i. Asratian and Khachatrian proved that connected Lo-graphs of order at least 3 are hamiltonian, thus improving Ore’s Theorem. All K1,3-free graphs are L1-graphs, whence recognizing hamiltonian L1-graphs is an NP-complete problem. The following results about L1-graphs, unifying known results of Ore-type and known results on K1,3-free graphs, are obtained. Set K = lcub;G|Kp,p+1 (contained within) G (contained within) KpV Kp+1 for some ρ ≥ }(vdenotesjoin
|
|
| 4. |
|
|
| 5. |
- Asratian, Armen S., et al.
(författare)
-
On the number of partial Steiner systems
- 2000
-
Ingår i: Journal of combinatorial designs (Print). - : John Wiley & Sons. - 1063-8539 .- 1520-6610. ; 8:5, s. 347-352
-
Tidskriftsartikel (refereegranskat)abstract
- We give a simple proof of the result of Grable on the asymptotics of the number of partial Steiner systems S(t,k,m).
|
|
| 6. |
- Asratian, Armen S., 1951-, et al.
(författare)
-
Some localization theorems on hamiltonian circuits
- 1990
-
Ingår i: Journal of combinatorial theory. Series B (Print). - : Elsevier. - 0095-8956 .- 1096-0902. ; 49:2, s. 287-294
-
Tidskriftsartikel (refereegranskat)abstract
- Theorems on the localization of the conditions of G. A. Dirac (Proc. London Math. Soc. (3), 2 1952, 69–81), O. Ore (Amer. Math. Monthly, 67 1960, 55), and Geng-hua Fan (J. Combin. Theory Ser. B, 37 1984, 221–227) for a graph to be hamiltonian are obtained. It is proved, in particular, that a connected graph G on p ≥ 3 vertices is hamiltonian if d(u) ≥ | M3(u)|/2 for each vertex u in G, where M3(u) is the set of vertices v in G that are a distance at most three from u.
|
|
| 7. |
- Asratian, Armen S., et al.
(författare)
-
Some panconnected and pancyclic properties of graphs with a local ore-type condition
- 1996
-
Ingår i: Graphs and Combinatorics. - 0911-0119 .- 1435-5914. ; 12:3, s. 209-219
-
Tidskriftsartikel (refereegranskat)abstract
- Asratian and Khachatrian proved that a connected graphG of order at least 3 is hamiltonian ifd(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| for any pathuwv withuv ∉ E(G), whereN(x) is the neighborhood of a vertexx.We prove that a graphG with this condition, which is not complete bipartite, has the following properties:a) For each pair of verticesx, y with distanced(x, y) ≥ 3 and for each integern, d(x, y) ≤ n ≤ |V(G)| − 1, there is anx − y path of lengthn. (b)For each edgee which does not lie on a triangle and for eachn, 4 ≤ n ≤ |V(G)|, there is a cycle of lengthn containinge. (c)Each vertex ofG lies on a cycle of every length from 4 to |V(G)|. This implies thatG is vertex pancyclic if and only if each vertex ofG lies on a triangle.
|
|
| 8. |
- Asratian, Armen S.
(författare)
-
Some results on an edge coloring problem of Folkman and Fulkerson
- 2000
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 223:1-3, s. 13-25
-
Tidskriftsartikel (refereegranskat)abstract
- In 1968, Folkman and Fulkerson posed the following problem: Let G be a graph and let (n1,...,nt) be a sequence of positive integers. Does there exist a proper edge coloring of G with colors 1,2,...,t such that precisely ni edges receive color i, for each i=1,...,t? If such a coloring exists then the sequence (n1,...,nt) is called color-feasible for G. Some sufficient conditions for a sequence to be color-feasible for a bipartite graph where found by Folkman and Fulkerson, and de Werra. In this paper we give a generalization of their results for bipartite graphs. Furthermore, we find a set of color-feasible sequences for an arbitrary simple graph. In particular, we describe the set of all sequences which are color-feasible for a connected simple graph G with Δ(G)3, where every pair of vertices of degree at least 3 are non-adjacent.
|
|
| 9. |
- Asratian, Armen S., 1951-, et al.
(författare)
-
Stable properties of graphs
- 1991
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 90:2, s. 143-152
-
Tidskriftsartikel (refereegranskat)abstract
- Abstract For many properties P Bondy and Chvátal (1976) have found sufficient conditions such that if a graph G + uv has property P then G itself has property P. In this paper we will give a generalization that will improve ten of these conditions.
|
|
| 10. |
- de Werra, D., et al.
(författare)
-
Complexity of some special types of timetabling problems
- 2002
-
Ingår i: Journal of Scheduling. - : John Wiley & Sons. - 1094-6136 .- 1099-1425. ; 5:2, s. 171-183
-
Tidskriftsartikel (refereegranskat)abstract
- Starting from the simple class-teacher model of timetabling (where timetables correspond to edgecolorings of a bipartite multigraph), we consider an extension defined as follows: we assume that the set of classes is partitioned into groups. In addition to the teachers giving lectures to individual classes, we have a collection of teachers who give all their lectures to groups of classes. We show that when there is one such teacher giving lectures to three groups of classes, the problem is NP-complete. We also examine the case where there are at most two groups of classes and we give a polynomial procedure based on network flows to find a timetable using at most t periods.
|
|
