Browse

You are looking at 41 - 50 of 91,392 items for

Open access

Ewa Drgas-Burchardt and Elżbieta Sidorowicz

Open access

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.

Open access

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 vV(G)1d(v)+1(1+max{d(v)d(v)+1-uN(v)1d(u)+1,0}) on α (G), where N(v) and d(v) = |N(v)| denote the neighborhood and the degree of a vertex vV (G), respectively. However, Selkow’s original proof of this result is incorrect. We give a new probabilistic proof of Selkow’s bound here.

Open access

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.

Open access

Joanna Cyman, Michael A. Henning and Jerzy Topp

Abstract

A dominating set of a graph G is a subset DVG 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 VG \ 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.

Open access

Izolda Gorgol

Abstract

We say that a graph F strongly arrows a pair of graphs (G,H) and write F ind(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 ind (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 ω2α2. This bound is sharp. Moreover we will also consider the case when G is not connected providing also a sharp lower bound which is linear in both parameters.

Open access

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 uvE(G). On the other hand, a graph G with γ×2 (G) = k is said to be k-γ×2+-stable if γ×2 (G + uv) = k for any uvE(G) and is said to be k-γ×2--stable if γ×2 (Guv) = k for any uvE(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 k-γ×2+-stable graphs and k-γ×2--stable graphs.

Open access

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 gG 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.

Open access

Teresa W. Haynes and Michael A. Henning

Abstract

Let G be a graph with vertex set V and no isolated vertices. A sub-set SV 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 γpr2(G)23n, and we characterize the extremal graphs achieving equality in the bound.

Open access

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 Xsc𝒫(G) of 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.