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: 8

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

A note on the Song-Zhang theorem for Hamiltonian graphs

100%
Zhao K., Gould R.
Colloquium Mathematicum
|
2010
|
tom 120
|
nr 1
63-75
EN
An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k+1, one of the following condition holds: (i) there exist u ≠ v ∈ S such that d(u) + d(v) ≥ n or |N(u) ∩ N(v)| ≥ α (G); (ii) for any distinct u and v in S, |N(u) ∪ N(v)| ≥ n - max{d(x): x ∈ S}, then G is Hamiltonian. We prove that if for each essential independent set S of cardinality k+1, one of conditions (i) or (ii) holds, then G is Hamiltonian. A number of known results on Hamiltonian graphs are corollaries of this result.
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

The structure and existence of 2-factors in iterated line graphs

81%
Ferrara M., Gould R., Hartke S.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
507-526
EN
We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where $L^k(G)$ contains a 2-factor.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Potential forbidden triples implying hamiltonicity: for sufficiently large graphs

81%
Faudree R., Gould R., Jacobson M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
273-289
EN
In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with $G_i = K_{1,3}$ for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁,G₂,G₃ such that all G₁G₂G₃-free graphs are hamiltonian. In this paper we consider the question of which triples (including $K_{1,s}$, s ≥ 3) of forbidden subgraphs potentially imply all sufficiently large graphs are hamiltonian. For s ≥ 4 we characterize these families.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Forbidden triples implying Hamiltonicity: for all graphs

81%
Faudree R., Gould R., Jacobson M.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
47-54
EN
In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with $G_i = K_{1,3}$ for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁, G₂, G₃ such that all G₁G₂G₃-free graphs are hamiltonian.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Chvátal-Erdös type theorems

71%
Faudree J., Faudree R., Gould R., Jacobson M., Magnant C.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
245-256
EN
The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1), and δ(G) ≥ α(G)+k-2, then G is hamiltonian. It is shown that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ 4k²+1, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected. This result supports the conjecture that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4.
7
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

62%
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.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Linear forests and ordered cycles

62%
Chen G., Faudree R., Gould R., Jacobson M., Lesniak L., Pfender F.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
359-372
EN
A collection $L = P¹ ∪ P² ∪ ... ∪ P^t$ (1 ≤ t ≤ k) of t disjoint paths, s of them being singletons with |V(L)| = k is called a (k,t,s)-linear forest. A graph G is (k,t,s)-ordered if for every (k,t,s)-linear forest L in G there exists a cycle C in G that contains the paths of L in the designated order as subpaths. If the cycle is also a hamiltonian cycle, then G is said to be (k,t,s)-ordered hamiltonian. We give sharp sum of degree conditions for nonadjacent vertices that imply a graph is (k,t,s)-ordered hamiltonian.
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ć.