A Chvátal-Erdös condition for (t, t)-factors in digraphs using given arcs

✍ Scribed by Pierre Fraisse; Oscar Ordaz

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 570 KB
• Volume: 71
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(88)90067-2

✦ Synopsis

Let D b a k-connected digraph with independence number (Y. We show that for any integers t and p such that k 3 $ti (t + 1) i-p, then any set of arcs of cardinal@ p inducing a subgraph with maximum in-and outdegree at most t is contained in a spanning subgraph which is regular of in-and out-degree t, called (t, t)-factor. We also Gnd the minimum number of arcs which insures for a k-connected oriented grapbr GE existence of a (t# t)-facto:.

RESUME

Soit D un digraphe k-fortement connexe de nombre de stabilitb LY. Nous montrons que pour tout couple d'entiets t, p v&ifiant k a $rt (t + 1) +p, alors tout ensemble dares de cardinal p qti induit un sous-graphe demi-degr& int&ieur et ext&ieur au plus t, est contenu darts un sous_graphe couvrant r&ulier de demi-degr& int&ieur et ext&ieur @?gal a t, appele (t, t)facteur. Nous donnons aussi une condition portant sur le nombre d"arcs qui garantit I'exsistence d'un (t, t)-facteur pour un graphe antisym&rique.