✦ LIBER ✦

Vertex-disjoint cycles containing prescribed vertices

✍ Scribed by Yoshiyasu Ishigami; Tao Jiang

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 206 KB
Volume: 42
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10090

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Enomoto 7 conjectured that if the minimum degree of a graph G of order n ≥ 4__k__ − 1 is at least the integer $ \left \lfloor \sqrt{n+\left (,{9 \over 4}k^2 - 4k + 1\right)} ,+ {3 \over 2}k - 1 \right \rfloor$, then for any k vertices, G contains k vertex‐disjoint cycles each of which contains one of the k specified vertices. We confirm the conjecture for n ≥ ck^2^ where c is a constant. Furthermore, we show that under the same condition the cycles can be chosen so that each has length at most six. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 276–296, 2003

📜 SIMILAR VOLUMES

Vertex-disjoint cycles containing specif

Vertex-disjoint cycles containing specified vertices in a bipartite graph

✍ Guantao Chen; Hikoe Enomoto; Ken-ichi Kawarabayashi; Katsuhiro Ota; Dingjun Lou; 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB

## Abstract A minimum degree condition is given for a bipartite graph to contain a 2‐factor each component of which contains a previously specified vertex. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 145–166, 2004

Edge disjoint cycles through specified v

Edge disjoint cycles through specified vertices

✍ Luis Goddyn; Ladislav Stacho 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB

## Abstract We give a sufficient condition for a simple graph __G__ to have __k__ pairwise edge‐disjoint cycles, each of which contains a prescribed set __W__ of vertices. The condition is that the induced subgraph __G__[__W__] be 2__k__‐connected, and that for any two vertices at distance two in _

Cycles intersecting a prescribed vertex

Cycles intersecting a prescribed vertex set

✍ Atsushi Kaneko; Akira Saito 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 425 KB

## Abstract A graph is said to have property __P__(__k,l__)(__k__ ⩾ __l__) if for any __X__ ∈ (^__G__^~__k__~) there exists a cycle such that |__X__ ∩ __V__(__C__)| = __l.__ Obviously an __n__‐connected graph (__n__ ⩾ 2) satisfies __P__(__n,n__). In this paper, we study parameters __k__ and __l__ s

Vertex disjoint routings of cycles over

Vertex disjoint routings of cycles over tori

✍ Jean-Claude Bermond; Min-Li Yu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB

## Abstract We study the problem of designing a survivable WDM network based on covering the communication requests with subnetworks that are protected independently from each other. We consider here the case when the physical network is __T__(__n__), a torus of size __n__ by __n__, the subnetworks

Vertex-disjoint cycles of length at most

Vertex-disjoint cycles of length at most four each of which contains a specified vertex

✍ Yoshiyas Ishigami 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB

## Abstract We obtain a sharp minimum degree condition δ (G) ≥ $\lfloor {\sqrt {\phantom{n^2}n+k^2-3k+1}}\rfloor + 2k-1$ of a graph __G__ of order __n__ ≥ 3__k__ guaranteeing that, for any __k__ distinct vertices, __G__ contains __k__ vertex‐disjoint cycles of length at most four each of which cont

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