Browsing by Subject "critical graphs"

Now showing 1 - 2 of 2

Access status: Open Access ,
On b-vertex and b-edge critical graphs
(2015) Eschouf, Noureddine Ikhlef; Blidia, Mostafa
A $b$-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the $b$-chromatic number $b(G)$ of a graph $G$ is the largest integer $k$ such that $G$ admits a $b$-coloring with $k$ colors. A simple graph $G$ is called $b^{+}$-vertex (edge) critical if the removal of any vertex (edge) of $G$ increases its b-chromatic number. In this note, we explain some properties in $b^{+}$-vertex (edge) critical graphs, and we conclude with two open problems.
Access status: Open Access ,
Weakly connected domination critical graphs
(2008) Lemańska, Magdalena; Patyk, Agnieszka
A dominating set $D \subset V(G)$ is a weakly connected dominating set in $G$ if the subgraph $G[D]_w = (N_{G}[D],E_w)$ weakly induced by $D$ is connected, where $E_{w}$ is the set of all edges with at least one vertex in $D$. The weakly connected domination number $\gamma_w(G)$ of a graph $G$ is the minimum cardinality among all weakly connected dominating sets in $G$. The graph is said to be weakly connected domination critical ($\gamma_w$-critical) if for each $u, v \in V(G)$ with $v$ not adjacent to $u$, $\gamma_w(G + vu) \lt \gamma_w (G)$. Further, $G$ is $k$-$\gamma_w$-critical if $\gamma_w(G)=k$ and for each edge $e \not\in E(G)$, $\gamma_w(G + e) \lt k$. In this paper we consider weakly connected domination critical graphs and give some properties of $3$-$\gamma_w$-critical graphs.