Search
Filters
total: 2328
-
Catalog
displaying 1000 best results Help
Search results for: STRONG PRODUCT GRAPHS
-
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...
-
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...
-
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...
-
Equitable colorings of some variation of corona products of cubic graphs
PublicationThe problem of determining the value of equitable chromatic number for multicoronas of cubic graphs is studied. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use almost optimal number of colors in the remaining cases.
-
Parity vertex colouring of graphs
PublicationA parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...
-
Community of Practice for Product Innovation Towards the Establishment of Industry 4.0
PublicationThe aim of this paper is to present the necessity of formulating the Community of Practice for Product Innovation process based on Cyber-Physical Production Systems towards the establishment of Industry 4.0. At this developing phase of Industry 4.0, there is a need to define a clear and more realistic approach for implementation process of Cyber-Physical Production Systems in manufacturing industries. Today Knowledge Management...
-
Multiacces quantum communication and product higher rank numerical range
PublicationIn the present paper we initiate the study of the product higher rank numerical range. The latter, being a variant of the higher rank numerical range, is a natural tool for study- ing a construction of quantum error correction codes for multiple access channels. We review properties of this set and relate it to other numerical ranges, which were recently introduced in the literature. Further, the concept is applied to the construction...
-
Strong ellipticity conditions and infinitesimal stability within nonlinear strain gradient elasticity
PublicationWe discuss connections between the strong ellipticity condition and the infinitesimal instability within the nonlinear strain gradient elasticity. The strong ellipticity (SE) condition describes the property of equations of statics whereas the infinitesimal stability is introduced as the positive definiteness of the second variation of an energy functional. Here we establish few implications which simplify the further analysis...
-
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”,...
-
Establishing intelligent enterprise through community of practice for product innovation
PublicationThis paper presents the idea of implementing the virtual Community of Practice for Product Innovation processes towards the establishment of intelligent enterprise. Since the fourth industrial revolution is passing through the developing phase, implementation of Cyber-Physical Production Systems require more realistic approach. Knowledge Management and Engineering plays an important role in manufacturing industries facing global...
-
Elgold partial: Amazon product reviews
Open Research DataThe dataset contains 34 Amazon product reviews in English. In each text, the named entities are marked. Each name entity is linked to the corresponding Wikipedia if possible. All entities were manually verified by at least three people, which makes the dataset a high-quality gold standard for the evaluation of named entity recognition and linking algorithms.
-
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.
-
On the size of identifying codes in triangle-free graphs
PublicationIn an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...
-
Degree product formula in the case of a finite group action
PublicationLet V, W be finite dimensional orthogonal representations of a finite group G. The equivariant degree with values in the Burnside ring of G has been studied extensively by many authors. We present a short proof of the degree product formula for local equivariant maps on V and W.
-
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...
-
Homoclinics for singular strong force Lagrangian systems in R^N
PublicationWe will be concerned with the existence of homoclinics for second order Hamiltonian systems in R^N (N>2) given by Hamiltonians of the form H(t,q,p)=Φ(p)+V(t,q), where Φ is a G-function in the sense of Trudinger, V is C^2-smooth, periodic in the time variable, has a single well of infinite depth at a point ξ and a unique strict global maximum 0 at the origin. Under a strong force type condition aroud the singular point ξ, we prove...
-
Experience Based Decisional DNA (DDNA) to Support Sustainable Product Design
PublicationThis paper presents the idea of providing engineering design knowledge to designers working on sustainable product design and development process. The new product development process often requires significant amount of design knowledge which can be saved and recalled by designers during the design process. This knowledge is very important for successful sustainable product development as it can include material selection, product...
-
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...
-
Synchronous black hole search in directed graphs
PublicationThe paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one...
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublicationAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublicationIn the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
-
Shallow-Water Acoustic Communications in Strong Multipath Propagation Conditions
PublicationA phenomenon that has a strong impact on signal transmission conditions in Underwater Acoustic Communication (UAC) systems is multipath propagation. As a result of multipath propagation, the transmitted signal undergoes time dispersion which results in inter-symbol interference observed on the receiving side. Time dispersion is large, especially in horizontal channels in shallow waters which significantly limits the transmission...
-
Sources of Market Information, Its Quality and New Product Financial Performance
PublicationWhile we observe a growing interest in the role of market information in new product development (NPD), existing research has still largely ignored the quality of market information that is a crucial issue in the era of the information society. What does affect the quality of market information in new product development projects, and how does this quality influence the financial performance of new products? In this paper, we address...
-
Strong-coupling superconductivity of SrIr2 and SrRh2 : Phonon engineering of metallic Ir and Rh
PublicationExperimental and theoretical studies on superconductivity in SrIr2 and SrRh2 Laves phases are presented. The measured resistivity, heat capacity, and magnetic susceptibility confirm the superconductivity of these compounds with Tc = 6.07 and 5.41 K, respectively. Electronic structure calculations show that the Fermi surface is mostly contributed by 5d (4d) electrons of Ir (Rh), with Sr atoms playing the role of electron donors....
-
On Symmetry of Uniform and Preferential Attachment Graphs
PublicationMotivated by the problem of graph structure compression under realistic source models, we study the symmetry behavior of preferential and uniform attachment graphs. These are two dynamic models of network growth in which new nodes attach to a constant number m of existing ones according to some attachment scheme. We prove symmetry results for m=1 and 2 , and we conjecture that for m≥3 , both models yield asymmetry with high...
-
Progress on Roman and Weakly Connected Roman Graphs
PublicationA graph G for which γR(G)=2γ(G) is the Roman graph, and if γwcR(G)=2γwc(G), then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar results for weakly connected Roman graphs. We also study Roman trees improving the result of M.A. Henning’s A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002)....
-
Equitable coloring of graphs. Recent theoretical results and new practical algorithms
PublicationIn this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.
-
The shadowing chain lemma for singular Hamiltonian systems involving strong forces
PublicationW niniejszym artykule rozważamy autonomiczny układ Hamiltonowski na płaszczyźnie z potencjałem, który ma punkt osobliwy (studnię nieskończonej głębokości) i maksimum globalne właściwe równe zero przyjmowane w dwóch różnych punktach płaszczyzny. Przy założeniu, że w otoczeniu punktu osobliwego potencjał spełnia warunek Gordona(gradient tego potencjału w otoczeniu punktu osobliwego jest tzw. silną siłą, ang. a strong force) dowodzimy...
-
Strong ellipticity within the Toupin–Mindlin first strain gradient elasticity theory
PublicationWe discuss the strong ellipticity (SE) condition within the Toupin–Mindlin first strain gradient elasticity theory. SE condition is closely related to certain material instabilities and describes mathematical properties of corresponding boundary-value problems. For isotropic solids, SE condition transforms into two inequalities in terms of five gradient-elastic moduli.
-
Conjectured strong complementary-correlations tradeoff
PublicationWe conjecture uncertainty relations that restrict correlations between the results of measurements performed by two separate parties on a shared quantum state. The first uncertainty relation bounds the sum of two mutual informations when one party measures a single observable and the other party measures one of two observables. The uncertainty relation does not follow from the Maassen-Uffink uncertainty relation and is much stronger...
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublicationIn the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.
-
Smart Virtual Product Development: Manufacturing Capability Analysis and Process Planning Module
PublicationSmart Virtual Product Development (SVPD) system provides effective use of information, knowledge, and experience in industry during the process of product development in Industry 4.0 scenario. This system comprises of three primary modules, each of which has been developed to cater to a need for digital knowledge capture for smart manufacturing in the areas of product design, production planning, and inspection planning. Manufacturing...
-
Two families of infinitely many homoclinics for singular strong force Hamiltonian systems
PublicationWe are concerned with a planar autonomous Hamiltonian system with a potential possessing a single well of infinite depth at a point X and a unique strict global maximum 0 at a point A. Under a strong force condition around the singularity X, via minimization of an action integral and using a shadowing chain lemma together with simple geometrical arguments, we prove the existence of infinitely many geometrically distinct homoclinic...
-
Towards Increasing Density of Relations in Category Graphs
PublicationIn the chapter we propose methods for identifying new associations between Wikipedia categories. The first method is based on Bag-of-Words (BOW) representation of Wikipedia articles. Using similarity of the articles belonging to different categories allows to calculate the information about categories similarity. The second method is based on average scores given to categories while categorizing documents by our dedicated score-based...
-
Product diversification, relative specialisation and economic development: import-export analysis.
PublicationThis paper contributes to trade diversification literature by comparing changes in relative (i.e. assessed in comparison with world patterns) heterogeneity of import and export structures in the process of economic development. In particular, by focusing on the diversification of imports, we add a missing piece to already analysed export trends. We use highly disaggregated trade statistics (4963 product lines) for 163 countries...
-
Smart Innovation Engineering System - A Tool for Facilitating Product Innovation Process
PublicationFor the survival and prosperity of the manufacturing unit, entrepreneurs need to find out new ideas that can be implemented in the products leading to innovation. The current study employs a systematic approach for product innovation. In this approach past experiences based on innovation decisions are stored and recalled during the innovation problem solving process. Implementing this system in the process of product innovation...
-
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
PublicationGiven a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree...
-
Optimal backbone coloring of split graphs with matching backbones
PublicationFor a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
-
Distributed Evacuation in Graphs with Multiple Exits
PublicationWe consider the problem of efficient evacuation using multiple exits. We formulate this problem as a discrete problem on graphs where mobile agents located in distinct nodes of a given graph must quickly reach one of multiple possible exit nodes, while avoiding congestion and bottlenecks. Each node of the graph has the capacity of holding at most one agent at each time step. Thus, the agents must choose their movements strategy...
-
Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs
PublicationThe problem of scheduling jobs on parallel machines under an incompatibility relation is considered in this paper. In this model, a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. We consider job scheduling under the incompatibility relation modeled by a bipartite graph, under the makespan optimality criterion, on uniform and unrelated machines. Unrelated machines...
-
Machine learning approach to packaging compatibility testing in the new product development process
PublicationThe paper compares the effectiveness of selected machine learning methods as modelling tools supporting the selection of a packaging type in new product development process. The main goal of the developed model is to reduce the risk of failure in compatibility tests which are preformed to ensure safety, durability, and efficacy of the finished product for the entire period of its shelf life and consumer use. This kind of testing...
-
A Semiautomatic Experience-Based Tool for Solving Product Innovation Problem
PublicationIn this paper we present the idea of Smart Innovation Engineering (SIE) System and its implementation methodology. The SIE system is semi-automatic system that helps in carrying the process of product innovation. It collects the experiential knowledge from the formal decisional events. This experiential knowledge is collected from the group of similar products having some common functions and features. The SIE system behaves like...
-
Connection graphs
Publication -
From unextendible product bases to genuinely entangled subspaces
PublicationUnextendible product bases (UPBs) are interesting mathematical objects arising in composite Hilbert spaces that have found various applications in quantum information theory, for instance in a construction of bound entangled states or Bell inequalities without quantum violation. They are closely related to another important notion, completely entangled subspaces (CESs), which are those that do not contain any fully separable pure...
-
Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
PublicationA team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented...
-
Support Product Development Framework by Means of Set of Experience Knowledge Structure (SOEKS) and Decisional DNA
PublicationIn this paper, we propose a framework to support product development activi-ties by utilizing Set of Experience Knowledge Structure (SOEKS) and Decisional DNA (DDNA). This idea will provide a new direction to researchers working on product development, especially designers and manufacturers. They will be working on the same platform and this will be reducing their communication gap. Once the final idea is perceived about product...
-
Strong mixing Markov semigroups on C1 are meager
PublicationDowodzi się, że zbiór tych półgrup operatorów Markowa na klasie Schattena C1, dla których w mocnej topologii operatorowej T(t) jest zbieżne do operatora Markowa Q, gdzie Q jest 1-wymiarową projekcją, jest zbiorem rzadkim w zbiorze wszystkich półgrup Markowa.
-
Natural Product Sciences
Journals -
NATURAL PRODUCT REPORTS
Journals -
A Framework for Searching in Graphs in the Presence of Errors
PublicationWe consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide...