✦ LIBER ✦

Covering the vertices of a digraph by cycles of prescribed length

✍ Scribed by D. Amar; A. Raspaud

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 427 KB
Volume: 87
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90041-y

No coin nor oath required. For personal study only.

✦ Synopsis

the vertices of a digraph by cycles of prescribed length, Discrete Mathematics 87 (

📜 SIMILAR VOLUMES

Covering the vertices of a graph by cycl

Covering the vertices of a graph by cycles of prescribed length

✍ D. Amar; I. Fournier; A. Germa 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB

The main theorem of that paper is the following: let G be a graph of order n, of size at least (nZ -3n + 6 ) / 2 . For any integers k, n,, n2,. . . , nk such that n = n, + n2 + ... + nk and n, 2 3, there exists a covering of the vertices of G by disjoint cycles (C,),=,..,k with ICjl = n,, except whe

Ranking the vertices of a weighted digra

Ranking the vertices of a weighted digraph using the length of forward arcs

✍ Mikio Kano; Akio Sakamoto 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 353 KB

A Polynomial Time Algorithm for Finding

A Polynomial Time Algorithm for Finding a Cycle Covering a Given Set of Vertices in a Semicomplete Multipartite Digraph

✍ Anders Yeo 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 181 KB

Covering the cliques of a graph with ver

Covering the cliques of a graph with vertices

✍ Paul Erdős; Tibor Gallai; Zsolt Tuza 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 681 KB

The following problem is investigated. Given an undirected graph G, determine the smallest cardinality of a vertex set that meets all complete subgraphs KC G maximal under inclusion.

Bounds of the longest directed cycle len

Bounds of the longest directed cycle length for minimal strong digraphs

✍ Zhi-bo Chen; Fu-ji Zhang 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 532 KB

In this paper we present the upper and lower bounds of the longest directed cycle length for minimal strr,ng digraphs in terms of the numbers of vertices and arcs. These bounds are both sharp. In addition, we give analogous results for minimal 2-edge connected graphs.

Cycles through Large Degree Vertices in

Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem

✍ Kenneth A. Berman; Xin Liu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let D=(V, E) be a digraph with vertex set V of size n and arc set E. For u # V, let d(u) denote the degree of u. A Meyniel set M is a subset of V such that d(u)+d(v) 2n&1 for every pair of nonadjacent vertices u and v belonging to M. In this paper we show that if D is strongly connected, then every