Wyniki wyszukiwania

1

Cycles in graphs and related problems

100%

Marczyk A.

Instytut Matematyczny Polskiej Akademii Nauk

EN

Our aim is to survey results in graph theory centered around four themes: hamiltonian graphs, pancyclic graphs, cycles through vertices and the cycle structure in a graph. We focus on problems related to the closure result of Bondy and Chvátal, which is a common generalization of two fundamental theorems due to Dirac and Ore. We also describe a number of proof techniques in this domain. Aside from the closure operation we give some applications of Ramsey theory in the research of cycle structure of graphs and present several methods used in the study of the structure of the set of cycle lengths in a hamiltonian graph.

2

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

A note on a new condition implying pancyclism

49%

Flandrin E., Li H., Marczyk A., Woźniak M.

Discussiones Mathematicae Graph Theory

|

2001

|

tom 21

|

nr 1

137-143

EN

We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to $K_{n/2,n/2}$.

3

A Note on Neighbor Expanded Sum Distinguishing Index

43%

Flandrin E., Li H., Marczyk A., Saclé J.-F., Woźniak M.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 1

29-37

EN

A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . . , k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.

4

Chvátal-Erdos condition and pancyclism

43%

Flandrin E., Li H., Marczyk A., Schiermeyer I., Woźniak M.

Discussiones Mathematicae Graph Theory

|

2006

|

tom 26

|

nr 2

335-342

EN

The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.

5

Arbitrarily vertex decomposable caterpillars with four or five leaves

43%

Cichacz S., Görlich A., Marczyk A., Przybyło J., Woźniak M.

Discussiones Mathematicae Graph Theory

|

2006

|

tom 26

|

nr 2

291-305

EN

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) of the vertex set of G such that for each i ∈ {1,...,k}, $V_i$ induces a connected subgraph of G on $a_i$ vertices. D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable caterpillars with four leaves. We also describe two families of arbitrarily vertex decomposable trees with maximum degree three or four.

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

5 Marczyk A.

4 Woźniak M.

3 Flandrin E.

3 Li H.

1 Cichacz S.

1 Görlich A.

1 Przybyło J.

1 Saclé J.-F.

1 Schiermeyer I.

1 2017

1 2008

2 2006

1 2001

Cycles in graphs and related problems

A note on a new condition implying pancyclism

A Note on Neighbor Expanded Sum Distinguishing Index

Chvátal-Erdos condition and pancyclism

Arbitrarily vertex decomposable caterpillars with four or five leaves