Advanced Search

>We prove that the domination number γ(T) of a tree T on n ≥ 3 vertices and with n₁ endvertices satisfies inequality γ(T) ≥ (n+2-n₁)/3 and we characterize the extremal graphs.

It is known that the removal of an edge from a graph G cannot decrease a domination number γ(G) and can increase it by at most one. Thus we can write that γ(G) ≤ γ(G-e) ≤ γ(G)+1 when an arbitrary edge e is removed. Here we present similar inequalities for the weakly connected domination number ${\gamma }_w$ and the connected domination number ${\gamma }_c$, i.e., we show that ${\gamma }_w\left(G\right)\le {\gamma }_w(G-e)\le {\gamma }_w\left(G\right)+1$ and ${\gamma }_c\left(G\right)\le {\gamma }_c(G-e)\le {\gamma }_c\left(G\right)+2$ if G and G-e are connected. Additionally we show that ${\gamma }_w\left(G\right)\le {\gamma }_w(G-Eₚ)\le {\gamma }_w\left(G\right)+p-1$ and ${\gamma }_c\left(G\right)\le {\gamma }_c(G-Eₚ)\le {\gamma }_c\left(G\right)+2p-2$ if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order p is a connected...

Nordhaus-Gaddum results for weakly convex domination number of a graph G are studied.

In [1] Burger and Mynhardt introduced the idea of universal fixers. Let G = (V, E) be a graph with n vertices and G’ a copy of G. For a bijective function π: V(G) → V(G’), define the prism πG of G as follows: V(πG) = V(G) ∪ V(G’) and $E\left(\pi G\right)=E\left(G\right)\cup E\left(G^{\text{'}}\right)\cup M_{\pi }$, where $M_{\pi }=u\pi \left(u\right)\left|u\in V\right(G)$. Let γ(G) be the domination number of G. If γ(πG) = γ(G) for any bijective function π, then G is called a universal fixer. In [9] it is conjectured that the only universal fixers are the edgeless graphs K̅ₙ. In this work we generalize the concept of universal...

A dominating set $D\subseteq V\left(G\right)$ is a in $G$ if the subgraph $G{\left[D\right]}_w=(N_G\left[D\right],E_w)$ weakly induced by $D$ is connected, where $E_w$ is the set of all edges having at least one vertex in $D$. ${\gamma }_w\left(G\right)$ of a graph $G$ is the minimum cardinality among all weakly connected dominating sets in $G$. A graph $G$ is said to be or just ${\gamma }_w$- if ${\gamma }_w\left(G\right)={\gamma }_w(G+e)$ for every edge $e$ belonging to the complement $\overline{G}$ of $G.$ We provide a constructive characterization of weakly connected domination stable trees.

For a given connected graph G = (V, E), a set $$D\subseteq V\left(G\right)$$ is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.

For a connected graph G = (V,E), a set D ⊆ V(G) is a dominating set of G if every vertex in V(G)-D has at least one neighbour in D. The distance $d_G(u,v)$ between two vertices u and v is the length of a shortest (u-v) path in G. An (u-v) path of length $d_G(u,v)$ is called an (u-v)-geodesic. A set X ⊆ V(G) is convex in G if vertices from all (a-b)-geodesics belong to X for any two vertices a,b ∈ X. A set X is a convex dominating set if it is convex and dominating. The convex domination number ${\gamma }_{con}\left(G\right)$ of a graph G is the...

The domination multisubdivision number of a nonempty graph G was defined in [3] as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. Similarly we define the total domination multisubdivision number msdγt (G) of a graph G and we show that for any connected graph G of order at least two, msdγt (G) ≤ 3. We show that for trees the total domination multisubdi- vision number is equal to the known total domination subdivision...

We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging...