>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 $γ_w$ and the connected domination number $γ_c$, i.e., we show that $γ_w(G) ≤ γ_w(G-e) ≤ γ_w(G)+1$ and $γ_c(G) ≤ γ_c(G-e) ≤ γ_c(G) + 2$ if G and G-e are connected. Additionally we show that $γ_w(G) ≤ γ_w(G-Eₚ) ≤ γ_w(G) + p - 1$ and $γ_c(G) ≤ γ_c(G -Eₚ) ≤ γ_c(G) + 2p - 2$ if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order p is a connected subgraph of G.
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(πG) = E(G) ∪ E(G') ∪ M_{π}$, where $M_{π} = {u π(u) | u ∈ V(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 fixers to the convex universal fixers. In the second section we give a characterization for convex universal fixers (Theorem 6) and finally, we give an in infinite family of convex universal fixers for an arbitrary natural number n ≥ 10.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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 number. We also determine the total domination multisubdivision number for some classes of graphs and characterize trees T with msdγt (T) = 1.
6
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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 to this family.
7
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
For a given connected graph G = (V, E), a set $$D \subseteq V(G)$$ 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 $γ_{con}(G)$ of a graph G is the minimum cardinality of a convex dominating set in G. Graphs with the convex domination number close to their order are studied. The convex domination number of a Cartesian product of graphs is also considered.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.