Javascript must be enabled to continue!

Certified domination critical graphs upon vertex removal

A set \(D\) of vertices of a graph \(G=(V_G,E_G)\) is a dominating set of \(G\) if every vertex in \(V_G-D\) is adjacent to at least one vertex in \(D\). The domination number of a graph \(G\), denoted by \(\gamma(G)\), is the cardinality of a smallest dominating set of \(G\). A subset \(D\subseteq V_G\) is called a certified dominating set of \(G\) if \(D\) is a dominating set of \(G\), and every vertex in \(D\) has either zero or at least two neighbours in \(V_G-D\). The cardinality of a smallest certified dominating set of \(G\) is called the certified domination number of \(G\), and it is denoted by \(\gamma_{\rm cer}(G)\). A vertex \(v\) of \(G\) is certified critical if \(\gamma_{\rm cer}(G -v) < \gamma_{\rm cer}(G)\), and a graph \(G\) is vertex certified domination critical or \(\gamma_{cer}\)-critical if the removal of any vertex reduces its certified domination number. In this paper, we give examples and properties of certified critical vertices and vertex certified domination critical graphs. As an example of an application of certified critical vertices, we give a constructive characterisation of trees for which the smaller partite set is a minimum certified dominating set.

Combinatorial Press

Mateusz Miotk

Utilitas Mathematica

2025

Title: Certified domination critical graphs upon vertex removal

Description:

The domination number of a graph \(G\), denoted by \(\gamma(G)\), is the cardinality of a smallest dominating set of \(G\).

A subset \(D\subseteq V_G\) is called a certified dominating set of \(G\) if \(D\) is a dominating set of \(G\), and every vertex in \(D\) has either zero or at least two neighbours in \(V_G-D\).

The cardinality of a smallest certified dominating set of \(G\) is called the certified domination number of \(G\), and it is denoted by \(\gamma_{\rm cer}(G)\).

A vertex \(v\) of \(G\) is certified critical if \(\gamma_{\rm cer}(G -v) < \gamma_{\rm cer}(G)\), and a graph \(G\) is vertex certified domination critical or \(\gamma_{cer}\)-critical if the removal of any vertex reduces its certified domination number.

In this paper, we give examples and properties of certified critical vertices and vertex certified domination critical graphs.

As an example of an application of certified critical vertices, we give a constructive characterisation of trees for which the smaller partite set is a minimum certified dominating set.

.

Back

Abstarct Introduction Isolated brain hydatid disease (BHD) is an extremely rare form of echinococcosis. A prompt and timely diagnosis is a crucial step in disease management. This ...

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

Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage

Abstract Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characteriz...

Completion and decomposition of hypergraphs by domination hypergraphs

A graph consists of a finite non-empty set of vertices and a set of unordered pairs of vertices, called edges. A dominating set of a graph is a set of vertices D such that every ve...

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

Failed Independent Number in Neutrosophic Graphs

New setting is introduced to study neutrosophic failed-independent number and failed independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key t...

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

2020 Statistical Profile of Certified PAs

Certified PAs Persevere Despite Pandemic Uncertainty Johns Creek, Ga., July 22, 2021 – Despite the uncertainty of the global pandemic, in 2020 Certified PAs largely maintained the...

Email:
Password:

Email:

Certified domination critical graphs upon vertex removal

Related Results