<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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 γ<sub>k</sub>(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.</p></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.

New results on connected dominating structures in graphs

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"New results on connected dominating structures in graphs"}

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

New results on connected dominating structures in graphs

Publicado en línea: 21 ago 2019

Páginas: 52 - 64

Recibido: 25 mar 2019

DOI: https://doi.org/10.2478/ausi-2019-0004

Palabras clave
dominating structure, clique domination, connected domination, strong product, tensor product

© 2019 Libin Chacko Samuel et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

New results on connected dominating structures in graphs

Publicado en línea: 21 ago 2019

Páginas: 52 - 64

Recibido: 25 mar 2019

DOI: https://doi.org/10.2478/ausi-2019-0004

Palabras clavedominating structure, clique domination, connected domination, strong product, tensor product

© 2019 Libin Chacko Samuel et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Palabras clave
dominating structure, clique domination, connected domination, strong product, tensor product