EUDML

The search session has expired. Please query the service again.

Currently displaying 1 – 4 of 4

Order by Relevance | Title | Year of publication

The Ryjáček Closure and a Forbidden Subgraph

Akira Saito; Liming Xiong — 2016

Discussiones Mathematicae Graph Theory

The Ryjáček closure is a powerful tool in the study of Hamiltonian properties of claw-free graphs. Because of its usefulness, we may hope to use it in the classes of graphs defined by another forbidden subgraph. In this note, we give a negative answer to this hope, and show that the claw is the only forbidden subgraph that produces non-trivial results on Hamiltonicity by the use of the Ryjáček closure.

Closure for spanning trees and distant area

Jun Fujisawa; Akira Saito; Ingo Schiermeyer — 2011

Discussiones Mathematicae Graph Theory

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with $d e g_{G} u + d e g_{G} v \geq n - 1$ , G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on $d e g_{G} u + d e g_{G} v$ and the structure of the distant area for u and v. We prove that if the...

2-factors in claw-free graphs

Guantao Chen; Jill R. Faudree; Ronald J. Gould; Akira Saito — 2000

Discussiones Mathematicae Graph Theory

We consider the question of the range of the number of cycles possible in a 2-factor of a 2-connected claw-free graph with sufficiently high minimum degree. (By claw-free we mean the graph has no induced $K_{1, 3}$ .) In particular, we show that for such a graph G of order n ≥ 51 with δ(G) ≥ (n-2)/3, G contains a 2-factor with exactly k cycles, for 1 ≤ k ≤ (n-24)/3. We also show that this result is sharp in the sense that if we lower δ(G), we cannot obtain the full range of values for k.

The Chvátal-Erdős condition and 2-factors with a specified number of components

Guantao Chen; Ronald J. Gould; Ken-ichi Kawarabayashi; Katsuhiro Ota; Akira Saito; Ingo Schiermeyer — 2007

Discussiones Mathematicae Graph Theory

Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components,...

Page 1

Download Results (CSV)

Advanced Search

Formula preview

Currently displaying 1 – 4 of 4

The Ryjáček Closure and a Forbidden Subgraph

Closure for spanning trees and distant area

2-factors in claw-free graphs

The Chvátal-Erdős condition and 2-factors with a specified number of components