Signed and minus domination in bipartite graphs

Bohdan Zelinka

Displaying similar documents to “Signed and minus domination in bipartite graphs”

Minus total domination in graphs

Hua Ming Xing, Hai-Long Liu (2009)

Czechoslovak Mathematical Journal

Similarity:

A three-valued function $f V \to {- 1, 0, 1}$ defined on the vertices of a graph $G = (V, E)$ is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every $v \in V$ , $f (N (v)) \geq 1$ , where $N (v)$ consists of every vertex adjacent to $v$ . The weight of an MTDF is $f (V) = \sum f (v)$ , over all vertices $v \in V$ . The minus total domination number of a graph $G$ , denoted $γ_{t}^{-} (G)$ , equals the minimum weight of an MTDF of $G$ . In this paper, we discuss some properties of minus total domination on a graph...

Domination numbers on the complement of the Boolean function graph of a graph

T. N. Janakiraman, S. Muthammai, M. Bhanumathi (2005)

Mathematica Bohemica

Similarity:

For any graph $G$ , let $V (G)$ and $E (G)$ denote the vertex set and the edge set of $G$ respectively. The Boolean function graph $B (G, L (G), N I N C)$ of $G$ is a graph with vertex set $V (G) \cup E (G)$ and two vertices in $B (G, L (G), N I N C)$ are adjacent if and only if they correspond to two adjacent vertices of $G$ , two adjacent edges of $G$ or to a vertex and an edge not incident to it in $G$ . For brevity, this graph is denoted by $B_{1} (G)$ . In this paper, we determine domination number, independent, connected, total, point-set, restrained, split and non-split domination...

Paired-domination

S. Fitzpatrick, B. Hartnell (1998)

Discussiones Mathematicae Graph Theory

Similarity:

We are interested in dominating sets (of vertices) with the additional property that the vertices in the dominating set can be paired or matched via existing edges in the graph. This could model the situation of guards or police where each has a partner or backup. This paper will focus on those graphs in which the number of matched pairs of a minimum dominating set of this type equals the size of some maximal matching in the graph. In particular, we characterize the leafless graphs of...

Total domination subdivision numbers of graphs

Teresa W. Haynes, Michael A. Henning, Lora S. Hopkins (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices in a graph G = (V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. The total domination subdivision number of G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. First we establish bounds on the total domination subdivision number...

Global domination and neighborhood numbers in Boolean function graph of a graph

T. N. Janakiraman, S. Muthammai, M. Bhanumathi (2005)

Mathematica Bohemica

Similarity:

For any graph $G$ , let $V (G)$ and $E (G)$ denote the vertex set and the edge set of $G$ respectively. The Boolean function graph $B (G, L (G), N I N C)$ of $G$ is a graph with vertex set $V (G) \cup E (G)$ and two vertices in $B (G, L (G), N I N C)$ are adjacent if and only if they correspond to two adjacent vertices of $G$ , two adjacent edges of $G$ or to a vertex and an edge not incident to it in $G$ . In this paper, global domination number, total global domination number, global point-set domination number and neighborhood number for this graph are obtained. ...

Graphs with disjoint dominating and paired-dominating sets

Justin Southey, Michael Henning (2010)

Open Mathematics

Similarity:

A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a dominating set such that the subgraph induced by the dominating set contains a perfect matching. In this paper, we show that no minimum degree is sufficient to guarantee the existence of a disjoint dominating set and a paired-dominating set. However, we prove that the vertex set of every cubic graph can be partitioned...

Signed degree sets in signed graphs

Shariefuddin Pirzada, T. A. Naikoo, F. A. Dar (2007)

Czechoslovak Mathematical Journal

Similarity:

The set $D$ of distinct signed degrees of the vertices in a signed graph $G$ is called its signed degree set. In this paper, we prove that every non-empty set of positive (negative) integers is the signed degree set of some connected signed graph and determine the smallest possible order for such a signed graph. We also prove that every non-empty set of integers is the signed degree set of some connected signed graph.