Wyniki wyszukiwania

1

The ramsey number for theta graph versus a clique of order three and four

100%

Bataineh M. S. A., Jaradat M. M. M., Bateeha M. S.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 2

223-232

EN

For any two graphs F1 and F2, the graph Ramsey number r(F1, F2) is the smallest positive integer N with the property that every graph on at least N vertices contains F1 or its complement contains F2 as a subgraph. In this paper, we consider the Ramsey numbers for theta-complete graphs. We determine r(θn,Km) for m = 2, 3, 4 and n > m. More specifically, we establish that r(θn,Km) = (n − 1)(m − 1) + 1 for m = 3, 4 and n > m

2

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

On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs

100%

Hałuszczak M.

Discussiones Mathematicae Graph Theory

|

2012

|

tom 32

|

nr 2

331-339

EN

Let F be a graph and let 𝓖,𝓗 denote nonempty families of graphs. We write F → (𝓖,𝓗) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (𝓖,𝓗)-minimal graph if F → (𝓖,𝓗) and F - e not → (𝓖,𝓗) for every e ∈ E(F). We present a technique which allows to generate infinite family of (𝓖,𝓗)-minimal graphs if we know some special graphs. In particular, we show how to receive infinite family of $(K_{1,2}, Kₙ)$-minimal graphs, for every n ≥ 3.

3

On constant-weight TSP-tours

51%

Jones S., Kayll P., Mohar B., Wallis W.

Discussiones Mathematicae Graph Theory

|

2003

|

tom 23

|

nr 2

287-307

EN

Is it possible to label the edges of Kₙ with distinct integer weights so that every Hamilton cycle has the same total weight? We give a local condition characterizing the labellings that witness this question's perhaps surprising affirmative answer. More generally, we address the question that arises when "Hamilton cycle" is replaced by "k-factor" for nonnegative integers k. Such edge-labellings are in correspondence with certain vertex-labellings, and the link allows us to determine (up to a constant factor) the growth rate of the maximum edge-label in a "most efficient" injective metric trivial-TSP labelling.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

1 Bataineh M. S. A.

1 Bateeha M. S.

1 Hałuszczak M.

1 Jaradat M. M. M.

1 Jones S.

1 Kayll P.

1 Mohar B.

1 Wallis W.

1 2014

1 2012

1 2003

The ramsey number for theta graph versus a clique of order three and four

On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs

On constant-weight TSP-tours