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

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

Differential graded vertex Lie algebras

This is the continuation of the study of differential graded (dg) vertex algebras defined in our previous paper [Caradot et al., “Differential graded vertex operator algebras and t...

Determination and Analysis of Domination Numbers for Boundary Graph and Boundary Neighbour Graph Using MATLAB

Vertex domination is a key concept in graph theory, essential for analyzing the structural properties of graphs. This study explores the use of vertex domination to determine the d...

On Non-Zero Vertex Signed Domination

For a graph G=(V,E) and a function f:V→{−1,+1}, if S⊆V then we write f(S)=∑v∈Sf(v). A function f is said to be a non-zero vertex signed dominating function (for short, NVSDF) of G ...

The Vertex-Edge Locating Roman Domination of Some Graphs

In this paper, we introduce the concept of vertex-edge locating Roman dominating functions in graphs. A vertex-edge locating Roman dominating (\({ve} - {LRD}\)) function of a graph...

The Vertex-Edge Locating Roman Domination of Some Graphs

In this paper, we introduce the concept of vertex-edge locating Roman dominating functions in graphs. A vertex-edge locating Roman dominating (\(ve-LRD\)) function of a graph \(G=(...

Email:
Password:

Email:

Certified domination critical graphs upon vertex removal

Related Results