Wyszukiwarka
Filtry
wszystkich: 121
wybranych: 83
Wyniki wyszukiwania dla: 3-UNIFORM HYPERGRAPH,SCHEDULING,EDGE-COLORING
-
Bounds on the vertex-edge domination number of a tree
PublikacjaA vertex-edge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertex-edge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(n-l-s+3)/4...
-
Computational aspects of greedy partitioning of graphs
PublikacjaIn 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...
-
T-colorings, divisibility and circular chromatic number
PublikacjaLet T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...
-
Energy efficient indoor localisation for narrowband internet of things
PublikacjaThere are an increasing number of Narrow Band IoT devices being manufactured as the technology behind them develops quickly. The high co-channel interference and signal attenuation was seen in edge Narrow Band IoT devices make it challenging to guarantee the service quality of these devices. To maximize the data rate fairness of Narrow Band IoT devices, a multi-dimensional indoor localization model is devised, consisting of...
-
Integration of Services into Workflow Applications
PublikacjaDescribing state-of-the-art solutions in distributed system architectures, Integration of Services into Workflow Applications presents a concise approach to the integration of loosely coupled services into workflow applications. It discusses key challenges related to the integration of distributed systems and proposes solutions, both in terms of theoretical aspects such as models and workflow scheduling algorithms, and technical...
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublikacjaIn 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...
-
Equitable coloring of corona products of graphs
PublikacjaIn this paper we consider an equitable coloring of some corona products of graphs G and H in symbols, G o H). In particular, we show that deciding the colorability of G o H is NP-complete even if G is 4-regular and H is K_2. Next, we prove exact values or upper bounds on the equitable chromatic number of G o H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph.
-
Domination subdivision and domination multisubdivision numbers of graphs
PublikacjaThe 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...
-
Three-fast-searchable graphs
PublikacjaIn 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...
-
Linear game non-contextuality and Bell inequalities—a graph-theoretic approach
PublikacjaWe study the classical and quantum values of a class of one-and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR(XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the...
-
On Symmetry of Uniform and Preferential Attachment Graphs
PublikacjaMotivated 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...
-
TOTAL DOMINATION MULTISUBDIVISION NUMBER OF A GRAPH
PublikacjaThe domination multisubdivision number of a nonempty graph G was defined in [3] as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. Similarly we define the total domination multisubdivision number msd_t (G) of a graph G and we show that for any connected graph G of order at least two, msd_t (G) ≤ 3. We show that for trees the total domination...
-
Experimental study of the impact of notches and holes made in the front edge of adherends on the properties of static and fatigue strength of adhesive joints
PublikacjaThe paper presents the results of experimental studies aimed at determining the effect of holes and notches at the front edge of adherends on the strength of adhesive joints. Single-lap joints made of S235JR steel sheets joined with Araldite 2014-2 epoxy adhesive were tested. Comparative tests of static strength in the shear test as well as high-cycle fatigue strength tests were carried out. Joints with three holes with a diameter...
-
Mobility Management Solutions for IP Networks Comparative Analysis of IP-based Mobility Protocols and Handover Algorithms Invited Paper
PublikacjaA rapid growth of IP-based networks and services hascreated a vast collection of resources and functionalities availableto users by means of a uniform method of access offered by the IPprotocol. At the same time, advances in the design of mobileelectronic devices allowed them to reach a utility levelcomparable to desktop computers, while still retaining theirmobility advantage. Unfortunately, the base IP protocol does notperform...
-
Axial capacity of steel built-up battened columns
PublikacjaThis paper deals with the numerical investigation aimed to study the axial capacity of pin-ended steel built-up columns. Three methods of calculating forces in chords and batten, taking into account the material and geometric imperfections specified in the Eurocode 3 are considered. The aim of this study was to compare different methods allowing the calculation of the column load capacity and determine a simpler and faster method...
-
On-line Ramsey Numbers of Paths and Cycles
PublikacjaConsider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of $G$ or a blue copy of $H$ for some fixed graphs $G$ and $H$. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the \emph{on-line Ramsey number} $\tilde{r}(G,H)$. In...
-
Mitigation of the Flow Maldistribution in Minichannel and Minigap Heat Exchangers by Introducing Threshold in the Manifolds
PublikacjaIn the present paper, a detailed numerical investigation has been carried out to analyze the flow maldistribution in 50 parallel rectangular cross-section (1 mm depth and 1 mm width) minichannels and minigap section (1 mm depth and 99 mm width) with rectangular/trapezoidal manifolds in Z-type flow configuration. The author carried out numerical investigation with various mass flowrates, namely 0.05 kg/s, 0.1 kg/s and 0.2 kg/s which...
-
Service time distribution influence on end-to-end call setup delay calculation in networks with Session Initiation Protocol
PublikacjaThe most important GoS parameter for networks with SIP protocol is end-to-end call setup delay. So far there were no coherent models allowing calculation of these parameters for networks with SIP protocol. Few models were developed but they are insufficient. In the paper we propose model which allows end-to-end call setup delay calculation for networks with SIP protocol. The model is using chain of M/G/1/K models and is applicable...
-
Graph Decomposition for Memoryless Periodic Exploration
PublikacjaWe 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...
-
Hybrid P3HT: PCBM/GaN nanowire/Si cascade heterojunction for photovoltaic application
PublikacjaPoly(3-hexylthiophene) (P3HT) and phenyl-C61-butyric acid methyl ester (PCBM) are commonly used for the fabrication of organic photovoltaics (OPV). Efficiency limitations of OPVs could be circumvented by incorporation of inorganic nanostructures into organic blends. Again, integration of organic solar cells with well-developed silicon photovoltaic technology is ultimately desirable. In present work, GaN nanowires with diameters...