Search
Filters
total: 155
filtered: 142
-
Catalog
Chosen catalog filters
Search results for: INDEPENDENT DOMINATION SUBDIVISION NUMBER
-
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...
-
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.
-
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...
-
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...
-
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 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}...
-
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.
-
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...
-
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”,...
-
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...
-
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...
-
Necessary and Sufficient Condition for State-Independent Contextual Measurement Scenarios
PublicationThe problem of identifying measurement scenarios capable of revealing state-independent contextuality in a given Hilbert space dimension is considered. We begin by showing that for any given dimension d and any measurement scenario consisting of projective measurements, (i) the measure of contextuality of a quantum state is entirely determined by its spectrum, so that pure and maximally mixed states represent the two extremes...
-
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...
-
Graphs with isolation number equal to one third of the order
PublicationA set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G, denoted by \iota(G) , is the minimum cardinality of an isolating set of G. It is known that \iota(G) \leq n/3 , if G is a connected graph of order n, , distinct from C_5 . The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number...
-
Relationship between semi- and fully-device-independent protocols
PublicationWe study the relation between semi and fully device independent protocols. As a tool, we use the correspondence between Bell inequalities and dimension witnesses. We present a method for converting the former into the latter and vice versa. This relation provides us with interesting results for both scenarios. First, we find new random number generation protocols with higher bit rates for both the semi and fully device independent...
-
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 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')...
-
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)....
-
Soft Sensor Application in Identification of the Activated Sludge Bulking Considering the Technological and Economical Aspects of Smart Systems Functioning
PublicationThe paper presented the methodology for the construction of a soft sensor used for activated sludge bulking identification. Devising such solutions fits within the current trends and development of a smart system and infrastructure within smart cities. In order to optimize the selection of the data-mining method depending on the data collected within a wastewater treatment plant (WWTP), a number of methods were considered, including:...
-
Robust four-node elements based on Hu–Washizu principle for nonlinear analysis of Cosserat shells
PublicationMixed 4-node shell elements with the drilling rotation and Cosserat-type strain measures based onthe three-field Hu–Washizu principle are proposed. In the formulation, apart from displacement and rotationfields, both strain and stress resultant fields are treated as independent. The elements are derived in the frame-work of a general nonlinear 6-parameter shell theory dedicated to the analysis of multifold irregular shells.The...
-
Reduced-order models in the finite element analysis
PublicationA novel technique of incorporating macromodels into finite element electromagnetic analysis of waveguide components is presented. Macromodels are generated by using a model order reduction algorithm (ENOR), which results in significant decrease of the number of variables, that describe the computational region. Proposed technique allows for using a few independent macromodels as well as to duplicating one macromodel in many subregions...
-
Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring
PublicationA graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...
-
Termination functions for evolutionary path planning algorithm
PublicationIn this paper a study of termination functions (stop criterion) for evolutionary path planning algorithm is presented. Tested algorithm is used to determine close to optimal ship paths in collision avoidance situation. For this purpose a path planning problem is defined. A specific structure of the individual path and fitness function is presented. For the simulation purposes a close to real tested environment is created. Five...
-
The Potential of Greed for Independence
PublicationThe well-known lower bound on the independence number of a graph due to Caro and Wei can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so-called potential functions p(G) : V(G) -> N_0 defined on the vertex set of a graph G for which suitably...
-
Possible uses of crisis situation aiding system in virtual world simulation
PublicationMany of the real world crisis situations like spreading fire, hostile units attack, flood, and etc. are commonly used in computer games where a simulation of extensive virtual world is crucial. This paper presents some ideas for possible uses of existing crisis situation aiding system in such environments. Moreover, it shows how this kind of system can be taught during subsequent games with a large number of players. As an example...
-
Report of the ISMIS 2011 Contest : Music Information Retrieval
PublicationThis report presents an overview of the data mining contestorganized in conjunction with the 19th International Symposiumon Methodologies for Intelligent Systems (ISMIS 2011), in days betweenJan 10 and Mar 21, 2011, on TunedIT competition platform. The contestconsisted of two independent tasks, both related to music information retrieval:recognition of music genres and recognition of instruments, for agiven music sample represented...
-
New potential functions for greedy independence and coloring
PublicationA potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...
-
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...
-
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...
-
Types of Markov Fields and Tilings
PublicationThe method of types is one of the most popular techniques in information theory and combinatorics. However, thus far the method has been mostly applied to one-dimensional Markov processes, and it has not been thoroughly studied for general Markov fields. Markov fields over a finite alphabet of size m ≥ 2 can be viewed as models for multi-dimensional systems with local interactions. The locality of these interactions is represented...
-
Collaborative Exploration of Trees by Energy-Constrained Mobile Robots
PublicationWe study the problem of exploration of a tree by mobile agents (robots) that have limited energy. The energy constraint bounds the number of edges that can be traversed by a single agent. We use a team of agents to collectively explore the tree and the objective is to minimize the size of this team. The agents start at a single node, the designated root of the tree and the height of the tree is assumed to be less than the energy...
-
On the Limiting distribution of Lempel Ziv'78 Redundancy for Memoryles Sources
PublicationWe show that the Lempel Ziv'78 redundancy rate tends to a Gaussian distribution for memoryless sources. We accomplish it by extending findings from our 1995 paper [3]. We present a new simplified proof of the Central Limit Theorem for the number of phrases in the LZ'78 algorithm. As in our 1995 paper, here we first analyze the asymptotic behavior of the total path length in a digital search tree (a DST) built from independent sequences....
-
Limiting distribution of Lempel Ziv'78 redundancy
PublicationWe show that the Lempel Ziv'78 redundancy rate tends to a Gaussian distribution for memoryless sources. We accomplish it by extending findings from our 1995 paper [3]. We present a new simplified proof of the Central Limit Theorem for the number of phrases in the LZ'78 algorithm. As in our 1995 paper, here we first analyze the asymptotic behavior of the total path length in a digital search tree (a DST) built from independent sequences....
-
Data fusion of GPS sensors using Particle Kalman Filter for ship dynamic positioning system
PublicationDepending on standards and class, dynamically positioned ships make use of different numbers of redundant sensors to determine current ship position. The paper presents a multi-sensor data fusion algorithm for the dynamic positioning system which allows it to record the proper signal from a number of sensors (GPS receivers). In the research, the Particle Kalman Filter with data fusion was used to estimate the position of the vessel....
-
Approximation algorithms for job scheduling with block-type conflict graphs
PublicationThe problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory...
-
Design-Oriented Constrained Modeling of Antenna Structures
PublicationFast surrogate models are crucially important to reduce the cost of design process of antenna structures. Due to curse of dimensionality, standard (data-driven) modeling methods exhibit serious limitations concerning the number of independent geometry parameters that can be handled but also (and even more importantly) their parameter ranges. In this work, a design-oriented modeling framework is proposed in which the surrogate is...
-
Applications of semi-definite optimization in quantum information protocols
PublicationThis work is concerned with the issue of applications of the semi-definite programming (SDP) in the field of quantum information sci- ence. Our results of the analysis of certain quantum information protocols using this optimization technique are presented, and an implementation of a relevant numerical tool is introduced. The key method used is NPA discovered by Navascues et al. [Phys. Rev. Lett. 98, 010401 (2007)]. In chapter...
-
Hybridized Space-Vector Pulsewidth Modulation for Multiphase Two-Level Voltage Source Inverter
PublicationIn space vector pulsewidth modulation (SVPWM) algorithms for multiphase two-level voltage source inverters (VSI), the components of active vectors in all orthogonal spaces have to be calculated within the processor and stored in its memory. These necessitate intensive computational efforts of the processor and large memory space. This article presents a hybridized SVPWM for multiphase two-level VSI. In this algorithm, elements...
-
Association of Genes Related to Oxidative Stress with the Extent of Coronary Atherosclerosis
PublicationOxidative stress is believed to play a critical role in atherosclerosis initiation and progression. In line with this, in a group of 1099 subjects, we determined eight single nucleotide polymorphisms (SNPs) related to oxidative stress (PON1 c.575A>G, MPO c.463G>A, SOD2 c.47T>C, GCLM c.590C>T, NOS3 c.894G>T, NOS3 c.786T>C, CYBA c.214C>T, and CYBA c.932A>G) and assessed the extent of atherosclerosis in coronary arteries based on...
-
Increased Certification of Semi-device Independent Random Numbers using Many Inputs and More Postprocessing
PublicationQuantum communication with systems of dimension larger than two provides advantages in information processing tasks. Examples include higher rates of key distribution and random number generation. The main disadvantage of using such multi-dimensional quantum systems is the increased complexity of the experimental setup. Here, we analyze a not-so-obvious problem: the relation between randomness certification and computational requirements...
-
On Dynamic Extension of a Local Material Symmetry Group for Micropolar Media
PublicationFor micropolar media we present a new definition of the local material symmetry group considering invariant properties of the both kinetic energy and strain energy density under changes of a reference placement. Unlike simple (Cauchy) materials, micropolar media can be characterized through two kinematically independent fields, that are translation vector and orthogonal microrotation tensor. In other words, in micropolar continua...
-
Rapid Design of 3D Reflectarray Antennas by Inverse Surrogate Modeling and Regularization
PublicationReflectarrays (RAs) exhibit important advantages over conventional antenna arrays, especially in terms of realizing pencil-beam patterns without the employment of the feeding networks. Unfortunately, microstrip RA implementations feature narrow bandwidths, and are severely affected by losses. A considerably improved performance can be achieved for RAs involving grounded dielectric layers, which are also easy to manufacture using...
-
On Design Optimization of Miniaturized Microscrip Dual-Band Rat-Race Coupler with Enhanced Bandwidth
PublicationIn the paper, a novel topology of a miniaturized wideband dual-band rat-race coupler has been presented. Small size of the circuit has been obtained by meandering transmission lines of the conventional circuit. At the same time, the number of independent geometry parameters has been increased in order to secure sufficient circuit flexibility in the context of its design optimization for dual-band operation. Optimum dimensions of...
-
Quantum security and theory of decoherence
PublicationWe sketch a relation between two crucial, yet independent, fields in quantum information research, viz. quantum decoherence and quantum cryptography. We investigate here how the standard cryptographic assumption of shielded laboratory, stating that data generated by a secure quantum device remain private unless explicitly published, is disturbed by the einselection mechanism of quantum Darwinism explaining the measurement process...
-
Wireless Link Selection Methods for Maritime Communication Access Networks—A Deep Learning Approach
PublicationIn recent years, we have been witnessing a growing interest in the subject of communication at sea. One of the promising solutions to enable widespread access to data transmission capabilities in coastal waters is the possibility of employing an on-shore wireless access infrastructure. However, such an infrastructure is a heterogeneous one, managed by many independent operators and utilizing a number of different communication...
-
Trade-offs in multiparty Bell-inequality violations in qubit networks
PublicationTwo overlapping bipartite binary input Bell inequalities cannot be simultaneously violated as this would contradict the usual no-signalling principle. This property is known as monogamy of Bell inequality violations and generally Bell monogamy relations refer to trade-offs between simultaneous violations of multiple inequalities. It turns out that multipartite Bell inequalities admit weaker forms of monogamies that allow for violations...
-
imPlatelet classifier: image‐converted RNA biomarker profiles enable blood‐based cancer diagnostics
PublicationLiquid biopsies offer a minimally invasive sample collection, outperforming traditional biopsies employed for cancer evaluation. The widely used material is blood, which is the source of tumor-educated platelets. Here, we developed the imPlatelet classifier, which converts RNA-sequenced platelet data into images in which each pixel corresponds to the expression level of a certain gene. Biological knowledge from the Kyoto Encyclopedia...
-
Coarse-grained simulation - an efficient approach for studying motions of large proteins
PublicationOne of the most important challenges in performing Molecular Dynamics (MD) simulations of large protein complexes is to accommodate the model accuracy and the simulation timescale. Hitherto, for the most relevant dynamics of protein aggregates in an explicit aqueous environment, the timescale reachable for the all-atoms simulations is of hundreds of nanoseconds. This range is four to six orders of magnitude smaller than processes...
-
On the Limiting Distribution of Lempel-Ziv’78 Redundancy for Memoryless Sources
PublicationWe study the Lempel-Ziv'78 algorithm and show that its (normalized) redundancy rate tends to a Gaussian distribution for memoryless sources. We accomplish it by extending findings from our 1995 paper, in particular, by presenting a new simplified proof of the central limit theorem (CLT) for the number of phrases in the LZ'78 algorithm. We first analyze the asymptotic behavior of the total path length in the associated digital search...
-
Elemental and tight monogamy relations in nonsignaling theories
PublicationPhysical principles constrain the way nonlocal correlations can be distributed among distant parties. These constraints are usually expressed by monogamy relations that bound the amount of Bell inequality violation observed among a set of parties by the violation observed by a different set of parties. We prove here that much stronger monogamy relations are possible for nonsignaling correlations by showing how nonlocal correlations...