Displaying similar documents to “Improving some bounds for dominating Cartesian products”

Some results on total domination in direct products of graphs

Paul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Spacapan (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.

On dominating the Cartesian product of a graph and K₂

Bert L. Hartnell, Douglas F. Rall (2004)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and...

A Note on the Locating-Total Domination in Graphs

Mirka Miller, R. Sundara Rajan, R. Jayagopal, Indra Rajasingh, Paul Manuel (2017)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we obtain a sharp (improved) lower bound on the locating-total domination number of a graph, and show that the decision problem for the locating-total domination is NP-complete.

New Bounds on the Signed Total Domination Number of Graphs

Seyyed Mehdi Hosseini Moghaddam, Doost Ali Mojdeh, Babak Samadi, Lutz Volkmann (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we study the signed total domination number in graphs and present new sharp lower and upper bounds for this parameter. For example by making use of the classic theorem of Turán [8], we present a sharp lower bound on Kr+1-free graphs for r ≥ 2. Applying the concept of total limited packing we bound the signed total domination number of G with δ(G) ≥ 3 from above by [...] . Also, we prove that γst(T) ≤ n − 2(s − s′) for any tree T of order n, with s support vertices and...

On the Complexity of Reinforcement in Graphs

Nader Jafari Rad (2016)

Discussiones Mathematicae Graph Theory

Similarity:

We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.

Some recent results on domination in graphs

Michael D. Plummer (2006)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; ...

Vizing's conjecture and the one-half argument

Bert Hartnell, Douglas F. Rall (1995)

Discussiones Mathematicae Graph Theory

Similarity:

The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as...

Relating 2-Rainbow Domination To Roman Domination

José D. Alvarado, Simone Dantas, Dieter Rautenbach (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which R(G) − yr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize...

Complete minors, independent sets, and chordal graphs

József Balogh, John Lenz, Hehui Wu (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ χ(G). Since χ(G) α(G) ≥ |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) ≥ |V(G)|. We show that (2α(G) - ⌈log_{τ}(τα(G)/2)⌉) h(G) ≥ |V(G)| where τ ≍ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V(G) | when α(G) ≥ 3.

Small Ramsey numbers.

Radziszowski, Stanisław P. (1996)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

On Vizing's conjecture

Bostjan Bresar (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.

Generalized domination, independence and irredudance in graphs

Mieczysław Borowiecki, Danuta Michalak, Elżbieta Sidorowicz (1997)

Discussiones Mathematicae Graph Theory

Similarity:

The purpose of this paper is to present some basic properties of 𝓟-dominating, 𝓟-independent, and 𝓟-irredundant sets in graphs which generalize well-known properties of dominating, independent and irredundant sets, respectively.

On partitions of hereditary properties of graphs

Mieczysław Borowiecki, Anna Fiedorowicz (2006)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper a concept 𝓠-Ramsey Class of graphs is introduced, where 𝓠 is a class of bipartite graphs. It is a generalization of well-known concept of Ramsey Class of graphs. Some 𝓠-Ramsey Classes of graphs are presented (Theorem 1 and 2). We proved that 𝓣₂, the class of all outerplanar graphs, is not 𝓓₁-Ramsey Class (Theorem 3). This results leads us to the concept of acyclic reducible bounds for a hereditary property 𝓟 . For 𝓣₂ we found two bounds (Theorem 4). An improvement,...

Lower bounds for integral functionals generated by bipartite graphs

Barbara Kaskosz, Lubos Thoma (2019)

Czechoslovak Mathematical Journal

Similarity:

We study lower estimates for integral fuctionals for which the structure of the integrand is defined by a graph, in particular, by a bipartite graph. Functionals of such kind appear in statistical mechanics and quantum chemistry in the context of Mayer's transformation and Mayer's cluster integrals. Integral functionals generated by graphs play an important role in the theory of graph limits. Specific kind of functionals generated by bipartite graphs are at the center of the famous and...

Domination, independence and irredundance in graphs

Jerzy Topp

Similarity:

CONTENTS1. Introduction........................................................................................................ 5 1.1. Purpose and scope................................................................................. 5 1.2. Basic graphtheoretical terms................................................................ 62. Domination, independence and irredundance in graphs................................ 9 2.1. Introduction and preliminaries.................................................................