Search
Filters
total: 78
Search results for: DOMINATION PARAMETERS
-
Interpolation properties of domination parameters of a graph
PublicationAn integer-valued graph function π is an interpolating function if a set π(T(G))={π(T): T∈TT(G)} consists of consecutive integers, where TT(G) is the set of all spanning trees of a connected graph G. We consider the interpolation properties of domination related parameters.
-
Relations between the domination parameters and the chromatic index of a graph
PublicationIn this paper we show bounds for the sum and the product of the domination parameters and the chromatic index of a graph. We alsopresent some families of graphs for which these bounds are achieved.
-
Domination-Related Parameters in Rooted Product Graphs
PublicationAbstract A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those sets of vertices of a graph satisfying some domination property together with other conditions on the vertices of G. Here, we investigate several domination-related parameters in rooted product graphs.
-
Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
PublicationGiven a graph G= (V, E), the subdivision of an edge e=uv∈E(G) means the substitution of the edge e by a vertex x and the new edges ux and xv. The domination subdivision number of a graph G is the minimum number of edges of G which must be subdivided (where each edge can be subdivided at most once) in order to increase the domination number. Also, the domination multisubdivision number of G is the minimum number of subdivisions...
-
Domination subdivision and domination multisubdivision numbers of graphs
PublicationThe domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...
-
On proper (1,2)‐dominating sets in graphs
PublicationIn 2008, Hedetniemi et al. introduced the concept of (1,)-domination and obtained some interesting results for (1,2) -domination. Obviously every (1,1) -dominating set of a graph (known as 2-dominating set) is (1,2) -dominating; to distinguish these concepts, we define a proper (1,2) -dominating set of a graph as follows: a subset is a proper (1,2) -dominating set of a graph if is (1,2) -dominating and it is not a (1,1) -dominating...
-
Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number
PublicationGiven two types of graph theoretical parameters ρ and σ, we say that a graph G is (σ, ρ)- perfect if σ(H) = ρ(H) for every non-trivial connected induced subgraph H of G. In this work we characterize (γw, τ )-perfect graphs, (γw, α′)-perfect graphs, and (α′, τ )-perfect graphs, where γw(G), τ (G) and α′(G) denote the weakly connected domination number, the vertex cover number and the matching number of G, respectively. Moreover,...
-
Common Independence in Graphs
PublicationAbstract: The cardinality of a largest independent set of G, denoted by α(G), is called the independence number of G. The independent domination number i(G) of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by αc(G), as the greatest integer r such that every vertex of G belongs to some independent subset X of VG with |X|...
-
Persulfates to degrade a mixture of dyes (rhodamine B, methylene blue) in the presence of glucose and visible light
PublicationA treatment process utilizing visible-light-activated (Vis) persulfates (PS) in the presence of an organic promoter (glucose) was developed for the simultaneous decolorization of a rhodamine B (RhB) and methylene blue (MB) mixture. Various doses of glucose, PS concentrations, pH values, initial dye concentrations and process time were tested to find out the most appropriate parameters for degrading the RhB/MB mixture in the...
-
On the connected and weakly convex domination numbers
PublicationIn this paper we study relations between connected and weakly convex domination numbers. We show that in general the difference between these numbers can be arbitrarily large and we focus on the graphs for which a weakly convex domination number equals a connected domination number. We also study the influence of the edge removing on the weakly convex domination number, in particular we show that a weakly convex domination number...
-
On domination multisubdivision number of unicyclic graphs
PublicationThe paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622–628], we constructively characterize all connected unicyclic graphs with...
-
TOTAL DOMINATION MULTISUBDIVISION NUMBER OF A GRAPH
PublicationThe 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...
-
Paired domination subdivision and multisubdivision numbers of graphs
PublicationThe paired domination subdivision number sdpr(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of G. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination muttisubdivision number of a nonempty graph...
-
Complexity Issues on of Secondary Domination Number
PublicationIn this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding...
-
Certified domination
PublicationImagine that we are given a set D of officials and a set W of civils. For each civil x ∈ W, there must be an official v ∈ D that can serve x, and whenever any such v is serving x, there must also be another civil w ∈ W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce...
-
On trees with equal domination and total outer-independent domination numbers
PublicationFor a graph G=(V,E), a subset D subseteq V(G) is a dominating set if every vertex of V(G)D has a neighbor in D, while it is a total outer-independent dominating set if every vertex of G has a neighbor in D, and the set V(G)D is independent. The domination (total outer-independent domination, respectively) number of G is the minimum cardinality of a dominating (total outer-independent dominating, respectively) set of G. We characterize...
-
On trees with equal 2-domination and 2-outer-independent domination numbers
PublicationFor a graph G = (V,E), a subset D \subseteq V(G) is a 2-dominating set if every vertex of V(G)\D$ has at least two neighbors in D, while it is a 2-outer-independent dominating set if additionally the set V(G)\D is independent. The 2-domination (2-outer-independent domination, respectively) number of G, is the minimum cardinality of a 2-dominating (2-outer-independent dominating, respectively) set of G. We characterize all trees...
-
Graphs with equal domination and certified domination numbers
PublicationA setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...
-
Influence of edge subdivision on the convex domination number
PublicationWe study the influence of edge subdivision on the convex domination number. We show that in general an edge subdivision can arbitrarily increase and arbitrarily decrease the convex domination number. We also find some bounds for unicyclic graphs and we investigate graphs G for which the convex domination number changes after subdivision of any edge in G.
-
On trees with double domination number equal to 2-domination number plus one
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A subset D subseteq V(G) is a 2-dominating set of G if every vertex of V(G)D is dominated by at least two vertices of D, while it is a double dominating set of G if every vertex of G is dominated by at least two vertices of D. The 2-domination (double domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (double dominating,...
-
On the ratio between 2-domination and total outer-independent domination numbers of trees
PublicationA 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D. A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The 2-domination (total outer-independent domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (total...
-
The paired-domination and the upper paired-domination numbers of graphs
PublicationIn this paper we obtain the upper bound for the upper paired-domination number and we determine the extremal graphs achieving this bound. Moreover we determine the upper paired- domination number for cycles.
-
2-outer-independent domination in graphs
PublicationWe initiate the study of 2-outer-independent domination in graphs. A 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D, and the set V(G)\D is independent. The 2-outer-independent domination number of a graph G is the minimum cardinality of a 2-outer-independent dominating set of G. We show that if a graph has minimum degree at least two,...
-
Unicyclic graphs with equal total and total outer-connected domination numbers
PublicationLet G = (V,E) be a graph without an isolated vertex. A set D ⊆ V (G) is a total dominating set if D is dominating and the in- duced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total domi- nating set of G. A set D ⊆ V (G) is a total outer–connected dominating set if D is total dominating and the induced subgraph G[V (G)−D] is a connected graph. The total outer–connected...
-
Weakly convex domination subdivision number of a graph
PublicationA set X is weakly convex in G if for any two vertices a; b \in X there exists an ab–geodesic such that all of its vertices belong to X. A set X \subset V is a weakly convex dominating set if X is weakly convex and dominating. The weakly convex domination number \gamma_wcon(G) of a graph G equals the minimum cardinality of a weakly convex dominating set in G. The weakly convex domination subdivision number sd_wcon (G) is the minimum...
-
On trees with double domination number equal to 2-outer-independent domination number plus one
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G is the minimum cardinality of a double dominating set of G. For a graph G=(V,E), a subset D subseteq V(G) is a 2-dominating set if every vertex of V(G)D has at least two neighbors...
-
On trees attaining an upper bound on the total domination number
PublicationA total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. The total domination number of a graph G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [Total and paired-domination numbers of a tree, AKCE International Journal of Graphs and Combinatorics 1 (2004), 69-75] established the following upper bound on the total domination...
-
On trees with double domination number equal to total domination number plus one
PublicationA total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The total (double, respectively) domination number of a graph G is the minimum cardinality of a total (double,...
-
An Alternative Proof of a Lower Bound on the 2-Domination Number of a Tree
PublicationA 2-dominating set of a graph G is a set D of vertices of G such that every vertex not in D has a at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. Fink and Jacobson [n-domination in graphs, Graph theory with applications to algorithms and computer science, Wiley, New York, 1985, 283-300] established the following lower bound on the 2-domination...
-
Total Domination Versus Domination in Cubic Graphs
PublicationA dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...
-
Block graphs with large paired domination multisubdivision number
PublicationThe paired domination multisubdivision number of a nonempty graph G, denoted by msdpr(G), is the smallest positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. It is known that msdpr(G) ≤ 4 for all graphs G. We characterize block graphs with msdpr(G) = 4.
-
Cops, a fast robber and defensive domination on interval graphs
PublicationThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
The convex domination subdivision number of a graph
PublicationLet G = (V;E) be a simple graph. A set D\subset V is a dominating set of G if every vertex in V - D has at least one neighbor 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\subset V is convex in G if vertices from all (a, b)-geodesics belong to X for any two vertices a, b \in X. A set X is a convex dominating...
-
Bondage number of grid graphs
PublicationThe bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. Here we study the bondage number of some grid-like graphs. In this sense, we obtain some bounds or exact values of the bondage number of some strong product and direct product of two paths.
-
On the super domination number of lexicographic product graphs
PublicationThe neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...
-
Weakly convex and convex domination numbers of some products of graphs
PublicationIf $G=(V,E)$ is a simple connected graph and $a,b\in V$, then a shortest $(a-b)$ path is called a $(u-v)$-{\it geodesic}. A set $X\subseteq V$ is called {\it weakly convex} in $G$ if for every two vertices $a,b\in X$ exists $(a-b)$- geodesic whose all vertices belong to $X$. A set $X$ is {\it convex} in $G$ if for every $a,b\in X$ all vertices from every $(a-b)$-geodesic belong to $X$. The {\it weakly convex domination number}...
-
Independent Domination Subdivision in Graphs
PublicationA set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in~$S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. The independent domination subdivision number $\sdi(G)$ is the minimum number of edges that must be subdivided (each...
-
Total domination in versus paired-domination in regular graphs
PublicationA subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...
-
All graphs with paired-domination number two less than their order
PublicationLet G=(V,E) be a graph with no isolated vertices. A set S⊆V is a paired-dominating set of G if every vertex not in S is adjacent with some vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination number γp(G) of G is defined to be the minimum cardinality of a paired-dominating set of G. Let G be a graph of order n. In [Paired-domination in graphs, Networks 32 (1998), 199-206] Haynes and Slater...
-
Seasonal changes of mercury speciation in the coastal sediments
PublicationPurpose Mercury speciation in sediments is linked to environmental conditions and processes. Domination of particular mercury species depends on its source, displays considerable seasonal behavior, and may be further modified due to oxygen levels, icing conditions, or the input of fresh organic matter. The purpose of this study was to examine the coastal area of the Gulf of Gdańsk in terms of mercury contamination and the influence...
-
Super Dominating Sets in Graphs
PublicationIn this paper some results on the super domination number are obtained. We prove that if T is a tree with at least three vertices, then n2≤γsp(T)≤n−s, where s is the number of support vertices in T and we characterize the extremal trees.
-
Valence state of Manganium in a MnCoO ceramics
Open Research DataManganium -cobalt based ceramics materials were produced by solid state reaction and sintred in a furnance in air atmosphere for 20h. Annealing temperature was 600 Celsius degree. For investigations a series of samples, with a various composition was chosen: MnCoO, Mn, Co2O and Mn2CoO. In order to determine valence states of the Mn, X-Ray photoemission...
-
Experimental and theoretical study of a vertical tube in shell storage unit with biodegradable PCM for low temperature thermal energy storage applications
PublicationThis article presents the experimental investigations of the coconut oil-based TES module for HVAC applications in the ambient and-sub ambient temperature range. To properly study this problem modular experimental module and test loop were developed. Special attention has been paid to study the physical mechanism of the melting/solidification process for natural substance (coconut oil) which has perspectives to be used in thermal...
-
Coronas and Domination Subdivision Number of a Graph
PublicationIn this paper, for a graph G and a family of partitions P of vertex neighborhoods of G, we define the general corona G ◦P of G. Among several properties of this new operation, we focus on application general coronas to a new kind of characterization of trees with the domination subdivision number equal to 3.
-
Distribution and bioavailability of mercury in the surface sediments of the Baltic Sea
PublicationThe study aimed to determine the level of mercury (Hg) and its labile and stable forms in the surface sediments of the Baltic Sea. The work considers the impact of current and historical sources of Hg on sediment pollution, together with the influence of different environmental parameters, including water inflows from the North Sea. Surface sediments (top 5 cm) were collected in 2016–2017 at 91 stations located in different...
-
Restrained differential of a graph
PublicationGiven a graph $G=(V(G), E(G))$ and a vertex $v\in V(G)$, the {open neighbourhood} of $v$ is defined to be $N(v)=\{u\in V(G) :\, uv\in E(G)\}$. The {external neighbourhood} of a set $S\subseteq V(G)$ is defined as $S_e=\left(\cup_{v\in S}N(v)\right)\setminus S$, while the \emph{restrained external neighbourhood} of $S$ is defined as $S_r=\{v\in S_e : N(v)\cap S_e\neq \varnothing\}$. The restrained differential of a graph $G$ is...
-
Preface of guest editors
PublicationA special issue of Discussiones Mathematice Graph Theory (DMGT) is dedicated to selected papers presented at the 12th Workshop on Graph Theory: Colourings, Independence and Domination (CID) held on 16-21 September 2007 in Karpacz, Poland. It continues a series of international workshops: 1993-1997 in Lubiatów, 1998-2001 in Gronów, 2003 and 2005 in Karpacz. About 70 participants formed the audience of six invited lectures and 68...
-
Secure Italian domination in graphs
PublicationAn Italian dominating function (IDF) on a graph G is a function f:V(G)→{0,1,2} such that for every vertex v with f(v)=0, the total weight of f assigned to the neighbours of v is at least two, i.e., ∑u∈NG(v)f(u)≥2. For any function f:V(G)→{0,1,2} and any pair of adjacent vertices with f(v)=0 and u with f(u)>0, the function fu→v is defined by fu→v(v)=1, fu→v(u)=f(u)−1 and fu→v(x)=f(x) whenever x∈V(G)∖{u,v}. A secure Italian dominating...
-
A lower bound on the total outer-independent domination number of a tree
PublicationA total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The total outer-independent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_t^{oi}(T) >= (2n-2l+2)/3,...
-
Bounds on the vertex-edge domination number of a tree
PublicationA vertex-edge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertex-edge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(n-l-s+3)/4...