Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Pairs of forbidden class of subgraphs concerning $K_{1,3}$ and P₆ to have a cycle containing specified vertices

100%

Sugiyama T., Tsugaki M.

Discussiones Mathematicae Graph Theory

|

2009

|

tom 29

|

nr 3

645-650

EN

In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1,3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1,3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.

2

Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

80%

Li B., Broersma H. J., Zhang S.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 4

915-929

EN

A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.

3

Potential forbidden triples implying hamiltonicity: for sufficiently large graphs

80%

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.

4

Forbidden Pairs and (k,m)-Pancyclicity

70%

Crane C. B.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 3

649-663

EN

A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs on n ≥ 10 vertices. There are exactly ten such pairs. For each integer k ≥ 1 and each of eight such subgraph pairs {R, S}, we determine the smallest value m such that any 2-connected {R, S}-free graph on n ≥ 10 vertices is guaranteed to be (k,m)-pancyclic. Examples are provided that show the given values are best possible. Each such example we provide represents an infinite family of graphs.

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

1 Broersma H. J.

1 Crane C. B.

1 Faudree R.

1 Gould R.

1 Jacobson M.

1 Li B.

1 Sugiyama T.

1 Tsugaki M.

1 Zhang S.

1 2017

1 2016

1 2009

1 2005

Pairs of forbidden class of subgraphs concerning $K_{1,3}$ and P₆ to have a cycle containing specified vertices

Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

Potential forbidden triples implying hamiltonicity: for sufficiently large graphs

Forbidden Pairs and (k,m)-Pancyclicity