Displaying similar documents to “New upper bound for a class of vertex Folkman numbers.”

On a Class of Vertex Folkman Numbers

Nenov, Nedyalko (2002)

Serdica Mathematical Journal

Similarity:

Let a1 , . . . , ar, be positive integers, i=1 ... r, m = ∑(ai − 1) + 1 and p = max{a1 , . . . , ar }. For a graph G the symbol G → (a1 , . . . , ar ) means that in every r-coloring of the vertices of G there exists a monochromatic ai -clique of color i for some i ∈ {1, . . . , r}. In this paper we consider the vertex Folkman numbers F (a1 , . . . , ar ; m − 1) = min |V (G)| : G → (a1 , . . . , ar ) and Km−1 ⊂ G} We prove that F (a1 , . . . , ar ; m − 1) = m + 6, if p = 3 and m ≧ 6...

On the Rainbow Vertex-Connection

Xueliang Li, Yongtang Shi (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ...

Rainbow Vertex-Connection and Forbidden Subgraphs

Wenjing Li, Xueliang Li, Jingshu Zhang (2018)

Discussiones Mathematicae Graph Theory

Similarity:

A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is defined as the minimum number of colors that are required to make G rainbow vertex-connected. In this paper, we find all the families ℱ of connected...

On rainbow connection.

Caro, Yair, Lev, Arie, Roditty, Yehuda, Tuza, Zsolt, Yuster, Raphael (2008)

The Electronic Journal of Combinatorics [electronic only]

Similarity: