Browse

You are looking at 81 - 90 of 91,274 items for

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.

Open access

Július Czap, Peter Šugerek, Stanislav Jendrol’ and Juraj Valiska

Abstract

Let G be a plane graph. Two edges are facially adjacent in G if they are consecutive edges on the boundary walk of a face of G. Given nonnegative integers r, s, and t, a facial [r, s, t]-coloring of a plane graph G = (V,E) is a mapping f : VE → {1, . . ., k} such that |f(v 1) − f(v 2)| ≥ r for every two adjacent vertices v 1 and v 2, |f(e 1) − f(e 2)| ≥ s for every two facially adjacent edges e 1 and e 2, and |f(v) − f(e)| ≥ t for all pairs of incident vertices v and edges e. The facial [r, s, t]-chromatic number ̄ χr,s,t(G) of G is defined to be the minimum k such that G admits a facial [r, s, t]-coloring with colors 1, . . ., k. In this paper we show that ̄ χr,s,t(G) ≤ 3r + 3s + t + 1 for every plane graph G. For some triplets [r, s, t] and for some families of plane graphs this bound is improved. Special attention is devoted to the cases when the parameters r, s, and t are small.

Open access

Monika Rosicka

Abstract

For a given graph G = (V;E) and permutation π : VV the prism πG of G is defined as follows: VG) = V (G) ∪ V (G′), where G′ is a copy of G, and E(πG) = E(G) ∪ E(G′) ∪M π, where M π = {uv′ : uV (G); v = π (u)} and v′ denotes the copy of v in G′.

We study and compare the properties of convex and weakly convex dominating sets in prism graphs. In particular, we characterize prism γcon-fixers and -doublers. We also show that the differences γwcon(G) – γwcon(πG) and γwcon (πG) – 2γwcon (G) can be arbitrarily large, and that the convex domination number of πG cannot be bounded in terms of γcon (G).