SwePub
Sök i SwePub databas

  Utökad sökning

Träfflista för sökning "L773:0012 365X OR L773:1872 681X ;lar1:(ltu)"

Sökning: L773:0012 365X OR L773:1872 681X > Luleå tekniska universitet

  • Resultat 1-2 av 2
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
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.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-2 av 2
Typ av publikation
tidskriftsartikel (2)
Typ av innehåll
refereegranskat (2)
Författare/redaktör
Asratian, Armen (1)
Kuzjurin, N. N. (1)
Asratian, Armen S. (1)
Lärosäte
Luleå tekniska universitet  (2)Ta bort avgränsningen
Språk
Engelska (2)
Forskningsämne (UKÄ/SCB)
Naturvetenskap (2)

År

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy