Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: traceable graph

Sortuj według:

Ogranicz wyniki do:

Dense Arbitrarily Partitionable Graphs

100%

Kalinowski R., Pilśniak M., Schiermeyer I., Woźniak M.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 1

5-22

A graph G of order n is called arbitrarily partitionable (AP for short) if, for every sequence (n1, . . . , nk) of positive integers with n1 + ⋯ + nk = n, there exists a partition (V1, . . . , Vk) of the vertex set V (G) such that Vi induces a connected subgraph of order ni for i = 1, . . . , k. In this paper we show that every connected graph G of order n ≥ 22 and with [...] ‖G‖ > (n−42)+12 $||G||\; > \;\left( {\matrix{{n - 4} \cr 2 \cr } } \right) + 12$ edges is AP or belongs to few classes of exceptional graphs.

The Ryjáček Closure and a Forbidden Subgraph

88%

Saito A., Xiong L.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 3

621-628

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Kalinowski R.

1 Pilśniak M.

1 Saito A.

1 Schiermeyer I.

1 Woźniak M.

1 Xiong L.

2 2016

Wyniki wyszukiwania

Dense Arbitrarily Partitionable Graphs

The Ryjáček Closure and a Forbidden Subgraph