Search results for: bipartite graph coloring
-
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...
-
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...
-
Southeastern International Conference on Combinatorics, Graph Theory, and Computing
Conferences -
Kyoto International Conference on Computational Geometry and Graph Theory
Conferences -
International Workshop on Graph-Theoretic Concepts in Computer Science
Conferences -
Nonrelational Databases DE 2024_2025
e-Learning CoursesThis course discusses three types of non-relational databases (i.e., document, graph, and key-value). The course is aimed at students in the 5th semester of data engineering.
-
Nonrelational Databases DE 2023_2024
e-Learning CoursesThis course discusses three types of non-relational databases (i.e., document, graph, and key-value). The course is aimed at students in the 5th semester of data engineering.
-
Computational algorithm for the analysis of mechatronic systems with distributed parameter elements
PublicationThe paper presents a systematic computational package for analysis of complex systems composed of multiple lumped and distributed parameter subsystems. The algorithm is based on the transfer function method (DTFM). With this algorithm, a bond graph technique for the modelling is developed to simplify computations. Analysis of different systems requires only changing the inputs data in the form of the bond graph diagram
-
Modelling of Mechatronic Systems with Distributed Parameter Components
PublicationThe paper presents an uniform, port-based approach to modelling of both lumped and distributed parameter systems. Port-based model of distributed system has been defined by application of the bond graph methodology and the distributed transfer function method (DTFM). The proposed method of modelling enables to formulate input data for computer analysis by application of the DTFM. The computational package for the analysis of complex...
-
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,...
-
An upper bound for the double outer-independent domination number of a tree
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent 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, and the set V(G)\D is independent. The double outer-independent domination number of a graph G, denoted by γ_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We prove...
-
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...
-
Non-relational Databases 2022/2023
e-Learning CoursesThis course discusses the three types of non-relational databases (i.e. document, graph, key-value). The course is aimed at students in the 7th semester of computer science.
-
Non-relational Databases 2023/2024
e-Learning CoursesThis course discusses the three types of non-relational databases (i.e. document, graph, key-value). The course is aimed at students in the 7th semester of computer science.
-
Non-relational Databases 2024/2025
e-Learning CoursesThis course discusses the three types of non-relational databases (i.e. document, graph, key-value). The course is aimed at students in the 7th semester of computer science.
-
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...
-
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...
-
Nonadditivity of quantum and classical capacities for entanglement breaking multiple-access channels and the butterfly network
PublicationWe analyze quantum network primitives which are entanglement breaking. We show superadditivity of quantum and classical capacity regions for quantum multiple-access channels and the quantum butterfly network. Since the effects are especially visible at high noise they suggest that quantum information effects may be particularly helpful in the case of the networks with occasional high noise rates. The present effects provide a qualitative...
-
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.
-
Total chromatic sum for trees
PublicationThe total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We provide infinite families of trees for which the minimum number of colors to achieve the total chromatic sum is equal to the total chromatic number. We construct infinite families of trees for which these numbers are not equal, disproving the conjecture from 2012.
-
Nonrelational Databases DE 2022_2023
e-Learning CoursesWithin this course the four types of non-relational databases (i.e. document, graph, key-value and column-oriented) are discussed. The course is aimed at students of the 5th semester of data engineering.
-
Some Progress on Total Bondage in Graphs
PublicationThe total bondage number b_t(G) of a graph G with no isolated vertex is the cardinality of a smallest set of edges E'⊆E(G) for which (1) G−E' has no isolated vertex, and (2) γ_t(G−E')>γ_t(G). We improve some results on the total bondage number of a graph and give a constructive characterization of a certain class of trees achieving the upper bound on the total bondage number.
-
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.
-
Conley-Morse graphs for a two-dimensional discrete neuron model (low resolution)
Open Research DataThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper “Topological-numerical analysis of a two-dimensional discrete neuron model” by Paweł Pilarczyk, Justyna Signerska-Rynkowska and Grzegorz Graff. A preprint of this paper is available at https://doi.org/10.48550/arXiv.2209.03443.
-
Conley-Morse graphs for a two-dimensional discrete neuron model (limited range)
Open Research DataThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper “Topological-numerical analysis of a two-dimensional discrete neuron model” by Paweł Pilarczyk, Justyna Signerska-Rynkowska and Grzegorz Graff. A preprint of this paper is available at https://doi.org/10.48550/arXiv.2209.03443.
-
Conley-Morse graphs for a two-dimensional discrete neuron model (full range)
Open Research DataThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper “Topological-numerical analysis of a two-dimensional discrete neuron model” by Paweł Pilarczyk, Justyna Signerska-Rynkowska and Grzegorz Graff. A preprint of this paper is available at https://doi.org/10.48550/arXiv.2209.03443.
-
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}...
-
A lower bound on the double outer-independent domination number of a tree
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent 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, and the set V(G)D is independent. The double outer-independent domination number of a graph G, denoted by gamma_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We...
-
Tight bounds on global edge and complete alliances in trees
PublicationIn the talk the authors present some tight upper bounds on global edge alliance number and global complete alliance number of trees. Moreover, we present our NP-completeness results from [8] for global edge alliances and global complete alliances on subcubic bipartite graphs without pendant vertices. We discuss also polynomial time exact algorithms for finding the minimum global edge alliance on trees [7] and complete alliance...
-
Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots
PublicationWe study two variants of delivery problems for mobile robots sharing energy. Each mobile robot can store at any given moment at most two units of energy, and whenever two robots are at the same location, they can transfer energy between each other, respecting the maximum capacity. The robots operate in a simple graph and initially each robot has two units of energy. A single edge traversal by an robot reduces its energy by one...
-
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...
-
Conley-Morse graphs for a non-linear Leslie population model with 2 varying parameters
Open Research DataThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "A database schema for the analysis of global dynamics of multiparameter systems" by Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka, P. Pilarczyk, published in SIAM Journal on Applied Dynamical Systems (SIADS),...
-
Conley-Morse graphs for a non-linear Leslie population model with 3 varying parameters
Open Research DataThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "A database schema for the analysis of global dynamics of multiparameter systems" by Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka, P. Pilarczyk, published in SIAM Journal on Applied Dynamical Systems (SIADS),...
-
Exploiting multi-interface networks: Connectivity and Cheapest Paths
PublicationLet G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...
-
On bipartization of cubic graphs by removal of an independent set
PublicationWe study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.
-
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...
-
On the Hat Problem on the Cycle C7
PublicationThe topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of a win. In this version every player can...
-
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...
-
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...
-
Embedded Representations of Wikipedia Categories
PublicationIn this paper, we present an approach to building neural representations of the Wikipedia category graph. We test four different methods and examine the neural embeddings in terms of preservation of graphs edges, neighborhood coverage in representation space, and their influence on the results of a task predicting parent of two categories. The main contribution of this paper is application of neural representations for improving the...
-
Collective Uncertainty Entanglement Test
PublicationFor a given pure state of a composite quantum system we analyze the product of its projections onto aset of locally orthogonal separable pure states. We derive a bound for this product analogous to theentropic uncertainty relations. For bipartite systems the bound is saturated for maximally entangled statesand it allows us to construct a family of entanglement measures, we shall call collectibility. As thesequantities are experimentally...
-
NO-BROADCASTING OF NON-SIGNALLING BOXES VIA OPERATIONS WHICH TRANSFORM LOCAL BOXES INTO LOCAL ONES
PublicationWe deal with families of probability distributions satisfying non-signalling condition, called non-signalling boxes and consider a class of operations that transform local boxes into local ones (the one that admit LHV model). We prove that any operation from this class cannot broadcast a bipartite non-local box with 2 binary inputs and outputs. We consider a function called anti-Robustness which can not decrease under these operations....
-
Deterministic Rendezvous in Restricted Graphs
PublicationIn this paper we consider the problem of synchronous rendezvous in which two anonymous mobile entities (robots) A and B are expected to meet at the same time and point in a graph G = (V;E). Most of the work devoted to rendezvous in graphs assumes that robots have access to the same sets of nodes and edges, where the topology of connections may be initially known or unknown. In our work we assume the movement of robots is restricted...
-
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,...
-
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...
-
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|...
-
Entanglement and Nonlocality are Inequivalent for Any Number of Parties
PublicationUnderstanding the relation between nonlocality and entanglement is one of the fundamental problems in quantum physics. In the bipartite case, it is known that these two phenomena are inequivalent, as there exist entangled states of two parties that do not violate any Bell inequality. However, except for a single example of an entangled three-qubit state that has a local model, almost nothing is known about such a relation in multipartite...
-
Dynamics of quantum entanglement
PublicationA model of discrete dynamics of entanglement of a bipartite quantum state is considered. It involves a global unitary dynamics of the system and periodic actions of local bistochastic or decaying channel. For initially pure states the decay of entanglement is accompanied by an increase of von Neumann entropy of the system. We observe and discuss revivals of entanglement due to unitary interaction of subsystems. For some mixed states...
-
All Nonclassical Correlations Can Be Activated into Distillable Entanglement
PublicationWe devise a protocol in which general nonclassical multipartite correlations produce a physically relevant effect, leading to the creation of bipartite entanglement. In particular, we show that the relative entropy of quantumness, which measures all nonclassical correlations among subsystems of a quantum system, is equivalent to and can be operationally interpreted as the minimum distillable entanglement generated between the system...
-
Software tool for modelling of mechatronic systems with elastic continua
PublicationThe paper presents a systematic computational package for modelling and analysis of complex systems composed of multiple lumped and distributed parameter subsystems. The constructed computer program enables the frequency domain analysis of a class of linear systems and to obtain reduced order model in the form of bond graph. Obtained modal bond graph can be directly exported into 20-Sim package to further processing including nonlinear...