### Denny Riama Silaban, Edy Tri Baskoro and Saladin Uttunggadewa

## Abstract

For any pair of graphs *G* and *H*, both the size Ramsey number ̂*r*(*G,H*) and the restricted size Ramsey number *r**(*G,H*) are bounded above by the size of the complete graph with order equals to the Ramsey number *r*(*G,H*), and bounded below by *e*(*G*) + *e*(*H*) − 1. Moreover, trivially, ̂*r*(*G,H*) ≤ *r**(*G,H*). When introducing the size Ramsey number for graph, Erdős *et al.* (1978) asked two questions; (1) Do there exist graphs *G* and *H* such that ˆ*r*(*G,H*) attains the upper bound? and (2) Do there exist graphs *G* and *H* such that ̂*r*(*G,H*) is significantly less than the upper bound?

In this paper we consider the restricted size Ramsey number *r**(*G,H*). We answer both questions above for *r**(*G,H*) when *G* = *P*
_{3} and *H* is a connected graph.

### Jochen Harant and Samuel Mohr

## Abstract

For a graph *G* with vertex set *V* (*G*) and independence number *α*(*G*), Selkow [*A Probabilistic lower bound on the independence number of graphs*, Discrete Math. 132 (1994) 363–365] established the famous lower bound *α* (*G*), where *N*(*v*) and *d*(*v*) = |*N*(*v*)| denote the neighborhood and the degree of a vertex *v* ∈ *V* (*G*), respectively. However, Selkow’s original proof of this result is incorrect. We give a new probabilistic proof of Selkow’s bound here.

### Ruxandra Marinescu-Ghemeci

## Abstract

Given a graph *G* and a vertex coloring *c*, *G* is called *l*-radio connected if between any two distinct vertices *u* and *v* there is a path such that coloring *c* restricted to that path is an *l*-radio coloring. The smallest number of colors needed to make *G l*-radio connected is called the *l*-radio connection number of *G*. In this paper we introduce these notions and initiate the study of connectivity through radio colored paths, providing results on the 2-radio connection number, also called *L*(2, 1)-connection number: lower and upper bounds, existence problems, exact values for known classes of graphs and graph operations.

### Joanna Cyman, Michael A. Henning and Jerzy Topp

## Abstract

A dominating set of a graph *G* is a subset *D* ⊆ *V _{G}* such that every vertex not in

*D*is adjacent to at least one vertex in

*D*. The cardinality of a smallest dominating set of

*G*, denoted by

*γ*(

*G*), is the domination number of

*G*. The accurate domination number of

*G*, denoted by

*γ*

_{a}(

*G*), is the cardinality of a smallest set

*D*that is a dominating set of

*G*and no |

*D*|-element subset of

*V*\

_{G}*D*is a dominating set of

*G*. We study graphs for which the accurate domination number is equal to the domination number. In particular, all trees

*G*for which

*γ*

_{a}(

*G*) =

*γ*(

*G*) are characterized. Furthermore, we compare the accurate domination number with the domination number of different coronas of a graph.

### Izolda Gorgol

## Abstract

We say that a graph *F strongly arrows* a pair of graphs (*G,H*) and write *F*
*G,H*) if any 2-coloring of its edges with red and blue leads to either a red *G* or a blue *H* appearing as induced subgraphs of *F*. *The induced Ramsey number*, *IR*(*G,H*) is defined as min{|*V* (*F*)| : *F*
*G,H*)}. We will consider two aspects of induced Ramsey numbers. Firstly we will show that the lower bound of the induced Ramsey number for a connected graph *G* with independence number α and a graph *H* with clique number *ω* is roughly *G* is not connected providing also a sharp lower bound which is linear in both parameters.

### Pawaton Kaemawichanurat

## Abstract

A graph *G* with the double domination number γ_{×2}(*G*) = *k* is said to be *k*- γ_{×2}-critical if γ_{×2} (*G* + *uv*) *< k* for any *uv* ∉ *E*(*G*). On the other hand, a graph *G* with γ_{×2} (*G*) = *k* is said to be _{×2} (*G* + *uv*) = *k* for any *uv* ∉ *E*(*G*) and is said to be _{×2} (*G*− *uv*) = *k* for any *uv* ∈ *E*(*G*). The problem of interest is to determine whether or not 2-connected *k*- γ_{×2}-critical graphs are Hamiltonian. In this paper, for *k* ≥ 4, we provide a 2-connected *k*- γ_{×2}-critical graph which is non-Hamiltonian. We prove that all 2-connected *k*-γ_{×2}-critical claw-free graphs are Hamiltonian when 2 ≤ *k* ≤ 5. We show that the condition claw-free when *k* = 4 is best possible. We further show that every 3-connected *k*- γ_{×2}-critical claw-free graph is Hamiltonian when 2 ≤ *k* ≤ 7. We also investigate Hamiltonian properties of

### Juan José Montellano-Ballesteros and Anahy Santiago Arguello

## Abstract

A variant of the Lovász Conjecture on hamiltonian paths states that *every finite connected Cayley graph contains a hamiltonian cycle*. Given a finite group *G* and a connection set *S*, the Cayley graph *Cay*(*G, S*) will be called *normal* if for every *g* ∈ *G* we have that *g*
^{−1}
*Sg* = *S*. In this paper we present some conditions on the connection set of a normal Cayley graph which imply the existence of a hamiltonian cycle in the graph.

### Teresa W. Haynes and Michael A. Henning

## Abstract

Let *G* be a graph with vertex set *V* and no isolated vertices. A sub-set *S* ⊆ *V* is a semipaired dominating set of *G* if every vertex in *V* \ *S* is adjacent to a vertex in *S* and *S* can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number γ_{pr2}(*G*) is the minimum cardinality of a semipaired dominating set of *G*. We show that if *G* is a connected graph *G* of order *n* ≥ 3, then

### Arnfried Kemnitz, Massimiliano Marangio and Margit Voigt

## Abstract

A (graph) property 𝒫 is a class of simple finite graphs closed under isomorphisms. In this paper we consider generalizations of sum list colorings of graphs with respect to properties 𝒫.

If to each vertex *v* of a graph *G* a list *L*(*v*) of colors is assigned, then in an (*L,* 𝒫)-coloring of *G* every vertex obtains a color from its list and the subgraphs of *G* induced by vertices of the same color are always in 𝒫. The 𝒫-sum choice number *G* is the minimum of the sum of all list sizes such that, for any assignment *L* of lists of colors with the given sizes, there is always an (*L,* 𝒫)-coloring of *G*.

We state some basic results on monotonicity, give upper bounds on the 𝒫-sum choice number of arbitrary graphs for several properties, and determine the 𝒫-sum choice number of specific classes of graphs, namely, of all complete graphs, stars, paths, cycles, and all graphs of order at most 4.