Search
Filters
total: 2826
-
Catalog
- Publications 2399 available results
- Journals 53 available results
- Conferences 27 available results
- Publishing Houses 1 available results
- People 64 available results
- Projects 6 available results
- e-Learning Courses 12 available results
- Events 5 available results
- Open Research Data 259 available results
displaying 1000 best results Help
Search results for: TRANSITION NETWORK GRAPHS
-
Multimodal Network Based Graphs of Primitives Storage Concept for Web Mining CBIR
Publication -
Mathematical modeling and prediction of pit to crack transition under cyclic thermal load using artificial neural network
PublicationThe formation of pitting is a major problem in most metals, which is caused by extremely localized corrosion that creates small holes in metal and subsequently, it changes into cracks under mechanical load, thermo-mechanical stress, and corrosion process factors. This research aims to study pit to crack transition phenomenon of steel boiler heat tubes under cyclic thermal load, and mathematical modeling...
-
Chronographic Imprint of Age-Induced Alterations in Heart Rate Dynamical Organization
PublicationBeat-to-beat changes in the heart period are transformed into a network of increments between subsequent RR-intervals, which enables graphical descriptions of short-term heart period variability. Three types of such descriptions are considered: (1) network graphs arising from a set of vertices and directed edges, (2) contour plots of adjacency matrices A, representing the networks and transition matrices T, resulting from A, and (3)...
-
Network on Chip implementation using FPGAs resources
PublicationW artykule przedstawiono implementację sieci typu ''Network on Chip'' w układach FPGA. Sieci typu ''Network on Chip'' stały się bardzo interesującym i obiecującym rozwiązaniem dla systemów typu ''System on Chip'' które charakteryzują się intensywną komunikacją wewnętrzną. Ze względu na inne paradygmaty projektowania nie ma obecnie dostępnych efektywnych platform do budowy prototypów sieci typu ''Network on Chip'' i ich weryfikacji....
-
GRAPHS AND COMBINATORICS
Journals -
Graph Decomposition for Memoryless Periodic Exploration
PublicationWe consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex v, the endpoints of all edges adjacent to v are assigned unique labels within the range 1 to deg (v) (the degree of v). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex...
-
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...
-
Dynamic F-free Coloring of Graphs
PublicationA problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...
-
Transition
Journals -
Strategic balance in graphs
PublicationFor a given graph G, a nonempty subset S contained in V ( G ) is an alliance iff for each vertex v ∈ S there are at least as many vertices from the closed neighbourhood of v in S as in V ( G ) − S. An alliance is global if it is also a dominating set of G. The alliance partition number of G was defined in Hedetniemi et al. (2004) to be the maximum number of sets in a partition of V ( G ) such that each set is an alliance. Similarly,...
-
Dynamic coloring of graphs
PublicationDynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...
-
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...
-
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...
-
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...
-
Interval incidence coloring of bipartite graphs
PublicationIn this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...
-
Smoothed transition curve for railways
PublicationThe work draws attention to the existing situation in the area of transition curves used in the geometric layouts of the railway track. Difficulties in the practical implementation and maintenance of very small horizontal ordinates of the transition curve and the ordinates of the gradient due to cant in the initial section, appearing on smooth transition curves, were indicated. The main reason for this situation was the excessive...
-
Global edge alliances in graphs
PublicationIn the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...
-
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.
-
Algorithms for testing security in graphs
PublicationIn this paper we propose new algorithmic methods giving with the high probability the correct answer to the decision problem of security in graphs. For a given graph G and a subset S of a vertex set of G we have to decide whether S is secure, i.e. every subset X of S fulfils the condition: |N[X] \cap S| >= |N[X] \ S|, where N[X] is a closed neighbourhood of X in graph G. We constructed a polynomial time property pseudotester based...
-
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...
-
On-line P-coloring of graphs
PublicationFor a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function...
-
Collision-free network exploration
PublicationMobile agents start at different nodes of an n-node network. The agents synchronously move along the network edges in a collision-free way, i.e., in no round two agents may occupy the same node. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest time required to reach a configuration in which each agent has visited all nodes and returned to its starting location. In...
-
A note on total reinforcement in graphs
PublicationIn this note we prove a conjecture and inprove some results presendet in a recent paper of N. Sridharan, M.D. Elias, V.S.A. Subramanian, Total reinforcement number of a graph, AKCE Int. J. Graphs Comb. 4 (2) (2007) 197-202.
-
On the metric dimension of corona product graphs
PublicationWe give several results on the metric dimension of corona product graphs.
-
Visualization of short-term heart period variability with network tools as a method for quantifying autonomic drive
PublicationWe argue that network methods are successful in detecting nonlinear properties in the dynamics of autonomic nocturnal regulation in short-term variability. Two modes of visualization of networks constructed from RR-increments are proposed. The first is based on the handling of a state space. The state space of RR-increments can be modified by a bin size used to code a signal and by the role of a given vertex as the representation...
-
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...
-
Prospects in elongation of railway transition curves
PublicationThe paper presents an analysis of the elongation of transition curves in relation to railway track alignment correction and modernisation. The analysis is based on numerical computations for a wide range of parameters describing a typical railway geometrical layout with transition curves. The differences between the horizontal ordinates of the existing layout and the layout with the elongated transition curves are evaluated and...
-
Edge and Pair Queries-Random Graphs and Complexity
PublicationWe investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.
-
Computational aspects of greedy partitioning of graphs
PublicationIn this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...
-
Collision-Free Network Exploration
PublicationA set of mobile agents is placed at different nodes of a n-node network. The agents synchronously move along the network edges in a collision-free way, i.e., in no round may two agents occupy the same node. In each round, an agent may choose to stay at its currently occupied node or to move to one of its neighbors. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest possible...
-
Colorings of the Strong Product of Circulant Graphs
PublicationGraph coloring is one of the famous problems in graph theory and it has many applications to information theory. In the paper we present colorings of the strong product of several circulant graphs.
-
Theory and Applications of Graphs
Journals -
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.
-
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')...
-
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,...
-
Navier number and transition to turbulence
PublicationThe motivation behind this article is to explain a role of the Navier number (Na -dimensionless slip-length) in prediction of closures for laminar to turbulent transition undergoing via eddies detachment from the slip layer in nano-cannals. Additionally the role of the Navier number Na in universal modeling of phenomenon of enhanced mass flow rate reported in micro- and nano-channels has been explained. The Na number should be...
-
Edge coloring of graphs of signed class 1 and 2
PublicationRecently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G, σ) it holds that ∆(G) ≤ χ′(G,σ) ≤ ∆(G) + 1, where ∆(G) is the maximum degree of G and χ′ denotes its chromatic index. In general, the chromatic index of (G, σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ′(G, σ) does not depend on σ. To this aim we...
-
The hat problem on a union of disjoint graphs
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 winning. In this version every player...
-
Transition dipole moments of the lithium dimer
PublicationIn addition to knowledge of interatomic adiabatic potential energy curves of diatomic systems, it is essential to know electronic transition dipole moments. They are needed in understanding processes like photodissociation, photoassociation, cooling, and trapping. Here, we present electronic transition dipole moments calculated for 74 allowed transitions between 26 states of Li2 [P. Jasik, J.E. Sienkiewicz, Chem. Phys. 323 (2006)...
-
On the super domination number of lexicographic product graphs
PublicationThe neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...
-
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|...
-
Maritime Communications Network Development Using Virtualised Network Slicing of 5G Network
PublicationThe paper presents the review on perspectives of maritime systems development at the context of 5G systems implementation and their main properties. Firstly, 5G systems requirements and principles are discussed, which can be important for maritime applications. Secondly, the problems of network softwarisation, virtualisation and slicing, and possible types of services for potential implementation in 5G marine applications are described....
-
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...
-
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...
-
Identification of transition curves in vehicular roads and railways
PublicationIn the paper attention is focused on the necessity to systematize the procedure for determining the shape of transition curves used in vehicular roads and railway routes. There has been presented a universal method of identifying curvature in transition curves by using differential equations. Curvature equations for such known forms of transition curves as clothoid, quartic parabola, the Bloss curve, cosinusoid and sinusoid, have...
-
Three-fast-searchable graphs
PublicationIn the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...
-
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.
-
Chromatic cost coloring of weighted bipartite graphs
PublicationGiven a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...
-
Asia in Transition
Journals -
On Computational Aspects of Greedy Partitioning of Graphs
PublicationIn this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...