Displaying similar documents to “On domination in graphs”

On the Totalk-Domination in Graphs

Sergio Bermudo, Juan C. Hernández-Gómez, José M. Sigarreta (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V, E) be a graph; a set S ⊆ V is a total k-dominating set if every vertex v ∈ V has at least k neighbors in S. The total k-domination number γkt(G) is the minimum cardinality among all total k-dominating sets. In this paper we obtain several tight bounds for the total k-domination number of a graph. In particular, we investigate the relationship between the total k-domination number of a graph and the order, the size, the girth, the minimum and maximum degree, the diameter,...

Some news about the independence number of a graph

Jochen Harant (2000)

Discussiones Mathematicae Graph Theory

Similarity:

For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G.

On the p-domination number of cactus graphs

Mostafa Blidia, Mustapha Chellali, Lutz Volkmann (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let p be a positive integer and G = (V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times. The minimum cardinality of a p-dominating set a of G is the p-domination number γₚ(G). It is proved for a cactus graph G that γₚ(G) ⩽ (|V| + |Lₚ(G)| + c(G))/2, for every positive integer p ⩾ 2, where Lₚ(G) is the set of vertices of G of degree at most p-1 and c(G) is the number of odd cycles in G.

Bounds on the Signed 2-Independence Number in Graphs

Lutz Volkmann (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a finite and simple graph with vertex set V (G), and let f V (G) → {−1, 1} be a two-valued function. If ∑x∈N|v| f(x) ≤ 1 for each v ∈ V (G), where N[v] is the closed neighborhood of v, then f is a signed 2-independence function on G. The weight of a signed 2-independence function f is w(f) =∑v∈V (G) f(v). The maximum of weights w(f), taken over all signed 2-independence functions f on G, is the signed 2-independence number α2s(G) of G. In this work, we mainly present upper bounds...

Sharp Upper Bounds on the Clar Number of Fullerene Graphs

Yang Gao, Heping Zhang (2018)

Discussiones Mathematicae Graph Theory

Similarity:

The Clar number of a fullerene graph with n vertices is bounded above by ⌊n/6⌋ − 2 and this bound has been improved to ⌊n/6⌋ − 3 when n is congruent to 2 modulo 6. We can construct at least one fullerene graph attaining the upper bounds for every even number of vertices n ≥ 20 except n = 22 and n = 30.

Relations between the domination parameters and the chromatic index of a graph

Włodzimierz Ulatowski (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective...

The bondage number of graphs: good and bad vertices

Vladimir Samodivkin (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph...

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

Lower bounds for the domination number

Ermelinda Delaviña, Ryan Pepper, Bill Waller (2010)

Discussiones Mathematicae Graph Theory

Similarity:

In this note, we prove several lower bounds on the domination number of simple connected graphs. Among these are the following: the domination number is at least two-thirds of the radius of the graph, three times the domination number is at least two more than the number of cut-vertices in the graph, and the domination number of a tree is at least as large as the minimum order of a maximal matching.

The Median Problem on k-Partite Graphs

Karuvachery Pravas, Ambat Vijayakumar (2015)

Discussiones Mathematicae Graph Theory

Similarity:

In a connected graph G, the status of a vertex is the sum of the distances of that vertex to each of the other vertices in G. The subgraph induced by the vertices of minimum (maximum) status in G is called the median (anti-median) of G. The median problem of graphs is closely related to the optimization problems involving the placement of network servers, the core of the entire networks. Bipartite graphs play a significant role in designing very large interconnection networks. In this...

Partitioning a graph into a dominating set, a total dominating set, and something else

Michael A. Henning, Christian Löwenstein, Dieter Rautenbach (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

Some Sharp Bounds on the Negative Decision Number of Graphs

Hongyu Liang (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A function f : V → {-1,1} is called a bad function of G if ∑u∈NG(v) f(u) ≤ 1 for all v ∈ V where NG(v) denotes the set of neighbors of v in G. The negative decision number of G, introduced in [12], is the maximum value of ∑v∈V f(v) taken over all bad functions of G. In this paper, we present sharp upper bounds on the negative decision number of a graph in terms of its order, minimum degree, and maximum degree. We also establish a sharp Nordhaus-Gaddum-type inequality...