Domination Critical Knodel Graphs

DOI10.1007/S40995-019-00710-8arXiv1805.01464MaRDI QIDQ6301136FDOQ6301136

Doost Ali Mojdeh, Seyed Reza Musawi, Esmaeil Nazari

Publication date: 3 May 2018

Abstract: A set $D$ of vertices of a graph $G$ is a dominating set if each vertex of $V(G)setminusD$ is adjacent to some vertex of $D$. The domination number of $G$, $gamma(G)$, is the minimum cardinality of a dominating set of $G$. A graph $G$ is called domination vertex critical, or just $gamma$-critical if removal of any vertex decreases the domination number. A graph $G$ is called domination vertex stable, or just $gamma$-stable, if removal of any vertex does not decrease the domination number. For an even integer $nge2$ and $1leDeltalelfloorlo{g}_{2}nfloor$, a Kn"odel graph $W_{Delta,n}$ is a $Delta$-regular bipartite graph of even order $n$, with vertices $(i,j)$, for $i=1,2$ and $0lejlen/2-1$, where for every $j$, $0lejlen/2-1$, there is an edge between vertex $(1,j)$ and every vertex $(2,j+2^k-1$ (mod (n/2)), for $k=0,1,cdots,Delta-1$. in this paper, we study the domination criticality and domination stability of Kn"odel graphs. We charactrize the 3-regular and 4-regular Kn"odel graphs by $gamma$-criticality or $gamma$-stability.

This page was built for publication: Domination Critical Knodel Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301136)