𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cycles intersecting a prescribed vertex set

✍ Scribed by Atsushi Kaneko; Akira Saito

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
425 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 such that every n‐connected graph satisfies P(k,l). We show that for r = 1 or 2 every n‐connected graph satisfies P(n + r,n). For r = 3, there are infinitely many 3‐connected graphs that do not satisfy P(6,3). However, if n ⩾ max{3,(2__r__ −1)(r + 1)}, then every n‐connected graph satisfies P(n + r,n).

📜 SIMILAR VOLUMES

Vertex-disjoint cycles containing prescr
Vertex-disjoint cycles containing prescribed vertices
✍ Yoshiyasu Ishigami; Tao Jiang 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 206 KB

## 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

On longest cycles and strongly linking v
On longest cycles and strongly linking vertex sets
✍ Bert Fassbender 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 245 KB 👁 1 views

Let G be a simple non-hamiltonian graph, let C be a longest cycle in G, and let p be a positive integer. By considering a special form of connectivity, we obtain a sufficient condition on degrees for the nonexistence of ( p -1)-path-connected components in G -C.

Hamiltonian cycles and paths with a pres
Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets
✍ Rostislav Caha; V. Koubek 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB 👁 1 views

## Abstract This paper studies techniques of finding hamiltonian paths and cycles in hypercubes and dense sets of hypercubes. This problem is, in general, easily solvable but here the problem was modified by the requirement that a set of edges has to be used in such path or cycle. The main result o

Vertex coverings by monochromatic paths
Vertex coverings by monochromatic paths and cycles
✍ A. Gyárfás 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB

We survey some results on covering the vertices of 2-colored complete graphs by t w o paths or by t w o cycles Qf different color. W e show the role of these results i n determining path Ramsey numbers and in algorithms for finding long monochromatic paths or cycles in 2-colored complete graphs. ##

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