Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
New results on connected dominating structures in graphs
View through CrossRef
Abstract
A set of vertices in a graph is a dominating set if every vertex not in the set is adjacent to at least one vertex in the set. A dominating structure is a subgraph induced by the dominating set. Connected domination is a type of domination where the dominating structure is connected. Clique domination is a type of domination in graphs where the dominating structure is a complete subgraph. The clique domination number of a graph G denoted by γk(G) is the minimum cardinality among all the clique dominating sets of G. We present few properties of graphs admitting dominating cliques along with bounds on clique domination number in terms of order and size of the graph. A necessary and sufficient condition for the existence of dominating clique in strong product of graphs is presented. A forbidden subgraph condition necessary to imply the existence of a connected dominating set of size four also is found.
Springer Science and Business Media LLC
Title: New results on connected dominating structures in graphs
Description:
Abstract
A set of vertices in a graph is a dominating set if every vertex not in the set is adjacent to at least one vertex in the set.
A dominating structure is a subgraph induced by the dominating set.
Connected domination is a type of domination where the dominating structure is connected.
Clique domination is a type of domination in graphs where the dominating structure is a complete subgraph.
The clique domination number of a graph G denoted by γk(G) is the minimum cardinality among all the clique dominating sets of G.
We present few properties of graphs admitting dominating cliques along with bounds on clique domination number in terms of order and size of the graph.
A necessary and sufficient condition for the existence of dominating clique in strong product of graphs is presented.
A forbidden subgraph condition necessary to imply the existence of a connected dominating set of size four also is found.
Related Results
Domination of Polynomial with Application
Domination of Polynomial with Application
In this paper, .We .initiate the study of domination. polynomial , consider G=(V,E) be a simple, finite, and directed graph without. isolated. vertex .We present a study of the Ira...
Nonsplit Neighbourhood Tree Domination Number In Connected Graphs
Nonsplit Neighbourhood Tree Domination Number In Connected Graphs
: Let G = (V, E) be a connected graph. A subset D of V is called a dominating set of G if N[D] = V. The minimum cardinality of a dominating set of G is called the domination number...
Weakly Modular Graphs and Nonpositive Curvature
Weakly Modular Graphs and Nonpositive Curvature
This article investigates structural, geometrical, and topological characterizations and properties of weakly modular graphs and of cell complexes derived from them. The unifying t...
DOMINATING COVER OF GRAPHS
DOMINATING COVER OF GRAPHS
Let $G=(V,E)$ be a simple graph. Then a set $S \subseteq V(G)$ is called a dominating set if every vertex $v \in V(G) \backslash S$ is adjacent to at least one vertex $u \in S$. Th...
An extension of locating-total domination problem and its complexity
An extension of locating-total domination problem and its complexity
An r-dominating set (r-total dominating set) of G is a subset S of V (G) for which Nr(u)∩S is non-empty for all u not in S (for all u in V (G)). An r-locating-dominating set (r-loc...
Changing and Unchanging Secure Integer Domination in Graphs
Changing and Unchanging Secure Integer Domination in Graphs
An Integer dominating function on a graph G is a function f : V (G) → W such that for every vertex
v ∈ V (G), . For any function f : V (G) → W and any pair of adjacent vertices w...
An Efficient Algorithm to Find Minimum Extended Dominating Set in Cactus Graphs: Application In Wireless Sensor Networks
An Efficient Algorithm to Find Minimum Extended Dominating Set in Cactus Graphs: Application In Wireless Sensor Networks
In a graph G and a positive integer k, a vertex set S, a subset of V is referred as a
k-extended dominating set of G if for each vertex u of V , either the distance between u and a...
Independent Set in Neutrosophic Graphs
Independent Set in Neutrosophic Graphs
New setting is introduced to study neutrosophic independent number and independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key term to have th...