Displaying similar documents to “New Bounds on the Signed Total Domination Number of Graphs”

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.

Packing of graphs

Woźniak Mariusz

Similarity:

PrefaceThere are two basic reference texts on packing theory: the last chapter of Bollobás's book [6] (1978) and the 4th chapter of Yap's book [85] (1986). They still remain the main references to packing problems. However, many papers related to these problems have recently been published and the reason for writing this survey is to gather in a systematic form results scattered throughout the literature.I wish I could name all who deserve my thanks. I am particularly grateful to A....

Labeled Embedding Of (n, n-2)-Graphs In Their Complements

M.-A. Tahraoui, E. Duchêne, H. Kheddouci (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Graph packing generally deals with unlabeled graphs. In [4], the authors have introduced a new variant of the graph packing problem, called the labeled packing of a graph. This problem has recently been studied on trees [M.A. Tahraoui, E. Duchêne and H. Kheddouci, Labeled 2-packings of trees, Discrete Math. 338 (2015) 816-824] and cycles [E. Duchˆene, H. Kheddouci, R.J. Nowakowski and M.A. Tahraoui, Labeled packing of graphs, Australas. J. Combin. 57 (2013) 109-126]. In this note, we...

Total domination in categorical products of graphs

Douglas F. Rall (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Several of the best known problems and conjectures in graph theory arise in studying the behavior of a graphical invariant on a graph product. Examples of this are Vizing's conjecture, Hedetniemi's conjecture and the calculation of the Shannon capacity of graphs, where the invariants are the domination number, the chromatic number and the independence number on the Cartesian, categorical and strong product, respectively. In this paper we begin an investigation of the total domination...

Improving some bounds for dominating Cartesian products

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

Discussiones Mathematicae Graph Theory

Similarity:

The study of domination in Cartesian products has received its main motivation from attempts to settle a conjecture made by V.G. Vizing in 1968. He conjectured that γ(G)γ(H) is a lower bound for the domination number of the Cartesian product of any two graphs G and H. Most of the progress on settling this conjecture has been limited to verifying the conjectured lower bound if one of the graphs has a certain structural property. In addition, a number of authors have established bounds...

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

Generalizations of the tree packing conjecture

Dániel Gerbner, Balázs Keszegh, Cory Palmer (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The Gyárfás tree packing conjecture asserts that any set of trees with 2,3,...,k vertices has an (edge-disjoint) packing into the complete graph on k vertices. Gyárfás and Lehel proved that the conjecture holds in some special cases. We address the problem of packing trees into k-chromatic graphs. In particular, we prove that if all but three of the trees are stars then they have a packing into any k-chromatic graph. We also consider several other generalizations of the conjecture. ...

On the Signed (Total) K-Independence Number in Graphs

Abdollah Khodkar, Babak Samadi, Lutz Volkmann (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph. A function f : V (G) → {−1, 1} is a signed k- independence function if the sum of its function values over any closed neighborhood is at most k − 1, where k ≥ 2. The signed k-independence number of G is the maximum weight of a signed k-independence function of G. Similarly, the signed total k-independence number of G is the maximum weight of a signed total k-independence function of G. In this paper, we present new bounds on these two parameters which improve some existing...

Packing Coloring of Some Undirected and Oriented Coronae Graphs

Daouya Laïche, Isma Bouchemakh, Éric Sopena (2017)

Discussiones Mathematicae Graph Theory

Similarity:

The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in G for every i, 1 ≤ i ≤ k. For a given integer p ≥ 1, the p-corona of a graph G is the graph obtained from G by adding p degree-one neighbors to every vertex of G. In this paper, we determine the packing chromatic number of p-coronae...

A Note on Uniquely Embeddable Forests

Justyna Otfinowska, Mariusz Woźniak (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let F be a forest of order n. It is well known that if F 6= Sn, a star of order n, then there exists an embedding of F into its complement F. In this note we consider a problem concerning the uniqueness of such an embedding.

Packing Parameters in Graphs

I. Sahul Hamid, S. Saravanakumar (2015)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G = (V,E), a non-empty set S ⊆ V is said to be an open packing set if no two vertices of S have a common neighbour in G. An open packing set which is not a proper subset of any open packing set is called a maximal open packing set. The minimum and maximum cardinalities of a maximal open packing set are respectively called the lower open packing number and the open packing number and are denoted by ρoL and ρo. In this paper, we present some bounds on these parameters. ...

A note on careful packing of a graph

M. Woźniak (1995)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an edge-disjoint placement of two copies of G into Kₙ. We prove that with the same condition on size of G we have actually (with few exceptions) a careful packing of G, that is an edge-disjoint placement of two copies of G into Kₙ∖Cₙ.