Search
Filters
total: 101
filtered: 100
Chosen catalog filters
Search results for: domination number
-
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...
-
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...
-
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...
-
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...
-
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...
-
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...
-
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...
-
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.
-
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,...
-
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...
-
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...
-
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...
-
Bipartite theory of graphs: outer-independent domination
PublicationLet $G = (V,E)$ be a bipartite graph with partite sets $X$ and $Y$. Two vertices of $X$ are $X$-adjacent if they have a common neighbor in $Y$, and they are $X$-independent otherwise. A subset $D \subseteq X$ is an $X$-outer-independent dominating set of $G$ if every vertex of $X \setminus D$ has an $X$-neighbor in $D$, and all vertices of $X \setminus D$ are pairwise $X$-independent. The $X$-outer-independent domination number...
-
angielski
PublicationA subset D of V (G) is a dominating set of a graph G if every vertex of V (G) − D has at least one neighbour in D; let the domination number γ(G) be the minimum cardinality among all dominating sets in G. We say that a graph G is γ-q-critical if subdividing any q edges results in a graph with domination number greater than γ(G) and there exists a set of q − 1 edges such that subdividing these edges results in a graph with domination...
-
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”,...
-
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.
-
Weakly connected Roman domination in graphs
PublicationA Roman dominating function on a graph G=(V,E) is defined to be a function f :V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v)=2. A dominating set D⊆V is a weakly connected dominating set of G if the graph (V,E∩(D×V)) is connected. We define a weakly connected Roman dominating function on a graph G to be a Roman dominating function such that the set...
-
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|...
-
Some variations of perfect graphs
PublicationWe 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...
-
2-bondage in graphs
PublicationA 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has 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. The 2-bondage number of G, denoted by b_2(G), is the minimum cardinality among all sets of edges E' subseteq E such that gamma_2(G-E') > gamma_2(G). If for every E' subseteq E we have...
-
Double bondage in graphs
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G=(V,E) 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, denoted by gamma_d(G), is the minimum cardinality of a double dominating set of G. The double bondage number of G, denoted by b_d(G), is the minimum cardinality among all sets...
-
Non-isolating 2-bondage in graphs
PublicationA 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has 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. The non-isolating 2-bondage number of G, denoted by b_2'(G), is the minimum cardinality among all sets of edges E' subseteq E such that delta(G-E') >= 1 and gamma_2(G-E') > gamma_2(G)....
-
Non-isolating bondage in graphs
PublicationA dominating set of a graph $G = (V,E)$ is a set $D$ of vertices of $G$ such that every vertex of $V(G) \setminus D$ has a neighbor in $D$. The domination number of a graph $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. The non-isolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(G-E') \ge 1$ and $\gamma(G-E')...
-
Pressure drop and heat transfer during boiling and condensation at subcritical region
PublicationMost of the data presented in the literature relate to saturation temperatures in the range - 20°C to 40°C due to the application in refrigeration technology. There is necessity to extend databases to higher values of saturation temperature due to new applications such as Organic Rankine Cycle and high temperature heat pumps. Only few papers contain data for high reduced pressure for low boiling point liquids. This paper focus...
-
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...
-
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.
-
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.
-
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...
-
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.
-
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...
-
Quantum strategies for rendezvous and domination tasks on graphs with mobile agents
PublicationThis paper explores the application of quantum nonlocality, a renowned and unique phenomenon acknowledged as a valuable resource. Focusing on an alternative application, we demonstrate its quantum advantage for mobile agents engaged in specific distributed tasks without communication. The research addresses the significant challenge of rendezvous on graphs and introduces a distributed task for mobile agents grounded in the graph...
-
Public spaces connecting cities. Green and Blue Infrastructures potential.
PublicationA city fragmentation causes a lot of negative effects in urban environment such as: disconnecting the environmental, functional and compositional relations, a loss of urban compactness, chaotic development, visual chaos, a domination of technical landscape, reduction of security. This is why one of main challenges for urban planners is to connect the fragmented structures by creating friendly, attractive and safe public space....
-
Preface
PublicationThis special issue of Discussiones Mathematice Graph Theory (DMGT) is dedicated to selected papers presented at the 13th Workshop on Graph Theory: Colourings, Independence and Domination (CID) held on 18-23 September 2009 in Szklarska Poręba, Poland. It continues a series of international workshops: 1993-1997 in Lubiatów, 1998-2001 in Gronów, and 2003-2007 in Karpacz. The meeting was organized by the Faculty of Mathematics, Computer...
-
Numerical modeling of exciton impact in two crystalographic phases of the organo-lead halide perovskite (CH3NH3PbI3) solar cell
PublicationTo improve the power conversion efficiency of solar cells based on organo–lead halide perovskites, a detailed understanding of the device physics is fundamental. Here, a computational analysis of excitons impact is reported for these types of photocell. Numerical calculations based on the model, which take into account electronic charge carriers (electrons and holes), excitons and ions, have been carried out. The role of excitons...
-
Activation of peroxymonosulfate using carbon black nano-spheres/calcium alginate hydrogel matrix for degradation of acetaminophen: Fe3O4 co-immobilization and microbial community response
PublicationHerein, we focused on the degradation of acetaminophen (ACT) drug in liquid phase by peroxymonosulfate (PMS) activated by carbon black nano-spheres (CBNS). The nanostructured activator was immobilized into calcium alginate hydrogel matrix (CAHM) to avoid the washout of the fine nanostructures. The Langmuir modeling showed an insignificant contribution to the adsorption process in the removal of ACT. The basic pH conditions favored...
-
Current status and future success of renewable energy in Pakistan
PublicationMismatch between energy demand and supply from last two decades has been increasing because of the domination of expensive imported oil in energy mix of Pakistan. To import crude oil Government paid US $ 9 billion in 2008–2009 to meet the energy demands...
-
Unexpected Z/E isomerism of N-methyl-O-phosphothioyl benzohydroxamic acids, their oxyphilic reactivity and inertness to amines
PublicationThiophosphinoylation of N-methyl p-substituted benzohydroxamic acids using disulfanes (method A) or diphenylphosphinothioyl chloride (method B) provides only one conformer of the respective O-phosphothioyl derivative (Xray and NMR analysis). Undergoing the P-transamidoxylation reaction is an evidence of the reversibility of thiophosphinoylation. Only those products containing strong EWG substituents in the aroyl residue or bulky...
-
Mutual Interaction between Temperature and DO Set Point on AOB and NOB Activity during Shortcut Nitrification in a Sequencing Batch Reactor in Terms of Energy Consumption Optimization
PublicationRecently, many wastewater treatment plants (WWTPs) have had to deal with serious problems related to the restrictive requirements regarding the euent quality, as well as significant energy consumption associated with it. In this situation, mainstream deammonification and/or shortened nitrification-denitrification via nitrite (so-called “nitrite shunt”) is a new promising strategy. This study shows the mechanisms and operating conditions...
-
Theoretical modelling of efficient fire safety water networks by certified domination
PublicationThis paper explores a new way of designing water supply networks for fire safety using ideas from graph theory, focusing on a method called certified domination. Ensuring a good water supply is crucial for fire safety in communities, this study looks at the rules and problems in Poland for how much water is needed to fight fires in different areas and how this can be achieved at a lowest possible cost. We present a way to plan...
-
The Urban Mentoring as a New Method of Participatory Urban Planning in Poland
PublicationTwenty-five years after the return of democracy and the beginning of basing the country's economy on neoliberal developmental paradigm, Poland adopted the regulations regarding management of urban policy, which had been wait for over a decade (accession to the EU). The National Urban Policy as well as the Act on revitalization have defined, in a modern manner, the field of cooperation between the local government, the administration...
-
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...
-
Modelling AOB-NOB competition in shortcut nitrification compared with conventional nitrification-denitrification process
PublicationIn particular, mainstream deammonification and/or shortened nitrificationdenitrification via nitrite (so-called “nitrite shunt”) is a promising new treatment concept that has the potential to revolutionise how nitrogen removal is achieved at WWTPs. Understanding the role of the AOB/NOB competition in the nitrogen cycle in wastewater treatment systems will change operational strategies of the novel nitrogen removal processes. The...
-
Noise Analysis of Continuous GPS Time Series of Selected EPN Stations to Investigate Variations in Stability of Monument Types
PublicationThe type of monument that a GPS antenna is placed on plays a significant role in noise estimation for each permanent GPS station. In this research 18 Polish permanent GPS stations that belong to the EPN (EUREF Permanent Network) were analyzed using Maximum Likelihood Estimation (MLE). The antennae of Polish EPN stations are placed on roofs of buildings or on concrete pillars. The analyzed data covers a period of 5 years from 2008...
-
THE INFLUENCE OF WATER-LAND RELATIONS ON THE LANDSCAPE AND ARCHITECTURE OF THE VISTULA DELTA (POLAND)
PublicationThe Vistula Delta is unique region of water domination. In this part of Europe, historic rural assumptions have been developing since the 12th century. Practically, it can be said that most of the systems were related to the coexistence of the human and the water element. Relations of water and land, developed specific types of villages such as a water-based village. Water landscape; polders, canals, dikes and rivers, hydro-technical...
-
5-Selenocyanato and 5-trifluoromethanesulfonyl derivatives of 2′-deoxyuridine: synthesis, radiation and computational chemistry as well as cytotoxicity
Publication5-Selenocyanato-2′-deoxyuridine (SeCNdU) and 5-trifluoromethanesulfonyl-2′-deoxyuridine (OTfdU) have been synthesized and their structures have been confirmed with NMR and MS methods. Both compounds undergo dissociative electron attachment (DEA) when irradiated with X-rays in an aqueous solution containing a hydroxyl radical scavenger. The DEA yield of SeCNdU significantly exceeds that of 5-bromo-2′-deoxyuridine (BrdU), remaining...
-
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...
-
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...
-
Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks
PublicationDominating sets find application in a variety of networks. A subset of nodes D is a (1,2)-dominating set in a graph G=(V,E) if every node not in D is adjacent to a node in D and is also at most a distance of 2 to another node from D. In networks, (1,2)-dominating sets have a higher fault tolerance and provide a higher reliability of services in case of failure. However, finding such the smallest set is NP-hard. In this paper, we...