Wyniki wyszukiwania

1

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

Pancyclism and small cycles in graphs

100%

Faudree R., Favaron O., Flandrin E., Li H.

Discussiones Mathematicae Graph Theory

|

1996

|

tom 16

|

nr 1

27-40

EN

We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (d_C(u,v)+1, [(n+19)/13]), $d_C(u,v)$ being the distance of u and v on a hamiltonian cycle of G.

2

Forbidden Pairs and (k,m)-Pancyclicity

88%

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.

3

On k-Path Pancyclic Graphs

88%

Bi Z., Zhang P.

Discussiones Mathematicae Graph Theory

|

2015

|

tom 35

|

nr 2

271-281

EN

For integers k and n with 2 ≤ k ≤ n − 1, a graph G of order n is k-path pancyclic if every path P of order k in G lies on a cycle of every length from k + 1 to n. Thus a 2-path pancyclic graph is edge-pancyclic. In this paper, we present sufficient conditions for graphs to be k-path pancyclic. For a graph G of order n ≥ 3, we establish sharp lower bounds in terms of n and k for (a) the minimum degree of G, (b) the minimum degree-sum of nonadjacent vertices of G and (c) the size of G such that G is k-path pancyclic

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

1 Bi Z.

1 Crane C. B.

1 Faudree R.

1 Favaron O.

1 Flandrin E.

1 Li H.

1 Zhang P.

1 2017

1 2015

1 1996

Pancyclism and small cycles in graphs

Forbidden Pairs and (k,m)-Pancyclicity

On k-Path Pancyclic Graphs