Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 4

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

The Ryjáček Closure and a Forbidden Subgraph

100%
Saito A., Xiong L.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
621-628
EN
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.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

2-factors in claw-free graphs

81%
Chen G., Faudree J., Gould R., Saito A.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
165-172
EN
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.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Closure for spanning trees and distant area

81%
Fujisawa J., Saito A., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
143-159
EN
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 $deg_G u + deg_G v ≥ 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 $deg_G u + deg_G v$ and the structure of the distant area for u and v. We prove that if the distant area contains $K_r$, we can relax the lower bound of $deg_G u + deg_G v$ from n-1 to n-r. And if the distant area itself is a complete graph and G is 2-connected, we can entirely remove the degree sum condition.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

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

61%
Chen G., Gould R., Kawarabayashi K.-i., Ota K., Saito A., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
401-407
EN
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, and (2) if n ≥ r(2a+3, a+1)+3(k-1), then G has a 2-factor with k components such that all components but one have order three.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.