| 1. |
- Asratian, Armen, et al.
(författare)
-
On the number of nearly perfect matchings in almost regular uniform hypergraphs
- 1999
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 207:1, s. 1-8
-
Tidskriftsartikel (refereegranskat)abstract
- Strengthening the result of R dl and Frankl (Europ. J. Combin 6 (1985) 317-326), Pippenger proved the theorem stating the existence of a nearly perfect matching in almost regular uniform hypergraph satisfying some conditions (see J. Combin. Theory A 51 (1989) 24-42). Grable announced in J. Combin. Designs 4 (4) (1996) 255-273 that such hypergraphs have exponentially many nearly perfect matchings. This generalizes the result and the proof in Combinatorica 11 (3) (1991) 207-218 which is based on the R dl Nibble algorithm (European J. Combin. 5 (1985) 69-78). In this paper, we present a simple proof of Grable's extension of Pippenger's theorem. Our proof is based on a comparison of upper and lower bounds of the probability for a random subgraph to have a nearly perfect matching. We use the Lovasz Local Lemma to obtain the desired lower bound of this probability.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- Asratian, Armen, et al.
(författare)
-
On interval edge colorings of (a, ß)-biregular bipartite graphs
- 2007
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 307:15, s. 1951-1956
-
Tidskriftsartikel (refereegranskat)abstract
- A bipartite graph G is called (a, ß)-biregular if all vertices in one part of G have degree a and all vertices in the other part have degree ß. An edge coloring of a graph G with colors 1, 2, 3, ..., t is called an interval t-coloring if the colors received by the edges incident with each vertex of G are distinct and form an interval of integers and at least one edge of G is colored i, for i = 1, ..., t. We show that the problem to determine whether an (a, ß)-biregular bipartite graph G has an interval t-coloring is NP-complete in the case when a = 6, ß = 3 and t = 6. It is known that if an (a, ß)-biregular bipartite graph G on m vertices has an interval t-coloring then a + ß - gcd (a, ß) = t = m - 1, where gcd (a, ß) is the greatest common divisor of a and ß. We prove that if an (a, ß)-biregular bipartite graph has m = 2 (a + ß) vertices then the upper bound can be improved to m - 3. © 2006 Elsevier B.V. All rights reserved.
|
|
