A Wireless Sensor Network (WSN) is a network composed of a large number of nodes that sense, collect, transmit, and deliver data to where it is needed. Considering the variety of applications, the varied efficiency of WSNs in different environments, and their ability to interact with its surrounding, there are still many challenges to be met and problems to be solved. Overcoming these challenges requires a protocol that is tasked with providing and designing a system that is highly efficient, thus saving energy. In WSNs with Mobile-Actors, the task is first to find an effective way to decrease the length of the tour that the M-Actor follows for data gathering. Nonetheless, this short length should be with a guarantee to access all nodes in the networks to collect the sensory data. In this thesis, we propose a protocol that contributes to reducing energy consumption in WSNs by decreasing the M-Actor path and by using Rendezvous Points (RPs) that are distributed around the network. In addition, the proposed protocol increases the network lifetime by consuming less energy in comparison with a similar protocol and offers reasonable spending time for data collection. All of that with guarantee of offering an access for all nodes inside the network to exchange their data with the M-Actors by the suggested RP algorithm. One or more nodes can be represented by a single RP that provide connectivity to all nodes in it wireless range. In case where more M-Actors are used, less time is required for traversing the network for data gathering. It is shown in this research the tour time can be reduced significantly by using more than one M-Actors.

No description available.

No description available.

Let G be a directed graph with a total labeling. The additive arc-weight of an arc xy is the sum of the label on xy and the label on y. The additive directed vertex-weight of a vertex x is the sum of the label on x and the labels on all arcs with head at x. The graph is additive arc magic if all additive arc-weights are equal, and is additive directed vertex magic if all vertex-weights are equal. We provide a complete characterization of all graphs which permit an additive arc magic labeling. A complete characterization of all regular graphs which may be oriented to permit an additive directed vertex magic labeling is provided. The definition of the subtractive arc-weight of an arc xy is proposed, and a correspondence between graceful labelings and subtractive arc magic labelings is shown.

Gene networks can be modeled by piecewise-linear (PL) switching systems of differential equations, called Glass networks after their originator. Networks of interacting genes that regulate each other may have complicated interactions. From a `systems biology' point of view, it would be useful to know what types of dynamical behavior are possible for certain classes of network interaction structure. A useful way to describe the activity of this network symbolically is to represent it as a directed graph on a hypercube of dimension $n$ where $n$ is the number of elements in the network. Our work here is considering this problem backwards, i.e. we consider different types of cycles on the $n$-cube and show that there exist parameters, consistent with the directed graph on the hypercube, such that a periodic orbit exists. For any simple cycle on the $n$-cube with a non-branching vertex, we prove by construction that it is possible to have a stable periodic orbit passing through the corresponding orthants for some sets of focal points $F$ in Glass networks. When the simple cycle on the $n$-cube doesn't have a non-branching vertex, a structural principle is given to determine whether it is possible to have a periodic orbit for some focal points. Using a similar construction idea, we prove that for self-intersecting cycles where the vertices revisited on the cycle are not adjacent, there exist Glass networks which have a periodic orbit passing through the corresponding orthants of the cycle. For figure-8 patterns with more than one common vertex, we obtain results on the form of the return map (Poincar{\'e} map) with respect to how the images of the returning cones of the 2 component cycle intersect the returning cone themselves. Some of these allow complex behaviors.

For 0 < |q| < 1, the q-numerical range is defined on the algebra Mn of all n x n complex matrices by Wq(A) ={x*Ay : x, y Є Cn , x*x = y*y = 1, x* y = q}. The q-numerical radius is defined by rq(A) = max{|μ| : μ Є Wq(A)}. We characterize isometries of the metric space (Mn , rq) i.e., the maps φ : Mn → Mn that satisfy rq(A - B) = rq(φ(A) - φ(B)). We also characterise maps on Mn that preserve the q-numerical range.

In this thesis we examine the computational complexity of certain digraph homomorphism problems. A homomorphism between digraphs, denoted by $f: G \to H$, is a mapping from the vertices of $G$ to the vertices of $H$ such that the arcs of $G$ are preserved. The problem of deciding whether a homomorphism to a fixed digraph $H$ exists is known as the $H$-colouring problem. We prove a generalization of a theorem due to Bang-Jensen, Hell and MacGillivray. Their theorem shows that for every semi-complete digraph $H$, $H$-colouring exhibits a dichotomy: $H$-colouring is either polynomial time solvable or it is NP-complete. We show that the class of local tournaments also exhibit a dichotomy. The NP-completeness results are found using direct NP-completeness reductions, indicator and vertex (and arc) sub-indicator constructions. The polynomial cases are handled by appealing to a result of Gutjhar, Woeginger and Welzl: the \underbar{$X$}-graft extension. We also provide a new proof of their result that follows directly from the consistency check. An unexpected result is the existence of unicyclic local tournaments with NP-complete homomorphism problems. During the last decade a new approach to studying the complexity of digraph homomorphism problems has emerged. This approach focuses attention on so-called polymorphisms as a measure of the complexity of a digraph homomorphism problem. For a digraph $H$, a polymorphism of arity $k$ is a homomorphism $f: H^k \to H$. Certain special polymorphisms are conjectured to be the key to understanding $H$-colouring problems. These polymorphisms are known as weak near unanimity functions (WNUFs). A WNUF of arity $k$ is a polymorphism $f: H^k \to H$ such that $f$ is idempotent an $f(y,x,x,\ldots,x)=f(x,y,x,\ldots,x)=f(x,x,y,\ldots,x) = \cdots = f(x,x,x,\ldots,y)$. We prove that a large class of polynomial time $H$-colouring problems all have a $\WNUF$. Furthermore we also prove some non-existence results for $\WNUF$s on certain digraphs. In proving these results, we develop a vertex (and arc) sub-indicator construction as well as an indicator construction in analogy with the ones developed by Hell and Ne{\v{s}}et{\v{r}}il. This is then used to show that all tournaments with at least two cycles do not admit a $\WNUF_k$ for $k>1$. This furnishes a new proof (in the case of tournaments) of the result by Bang-Jensen, Hell and MacGillivray referred to at the start. These results lend some support to the conjecture that $\WNUF$s are the ``right'' functions for measuring the complexity of $H$-colouring problems. We also study a related notion, namely that of an injective homomorphism. A homomorphism $f: G \to H$ is injective if the restriction of $f$ to the in-neighbours of every vertex in $G$ is an injective mapping. In order to classify the complexity of these problems we develop an indicator construction that is suited to injective homomorphism problems. For this type of digraph homomorphism problem we consider two cases: reflexive and irreflexive targets. In the case of reflexive targets we are able to classify all injective homomorphism problems as either belonging to the class of polynomial time solvable problems or as being NP-complete. Irreflexive targets pose more of a problem. The problem lies with targets of maximum in-degree equal to two. Targets with maximum in-degree one are polynomial, while targets with in-degree at least three are NP-complete. There is a transformation from (ordinary) graph homomorphism problems to injective, in-degree two, homomorphism problems (a reverse transformation also exists). This transformation provides some explanation as to the difficulty of the in-degree two case. We nonetheless classify all injective homomorphisms to irreflexive tournaments as either being a problem in P or a problem in the class of NP-complete problems. We also discuss some upper bounds on the injective oriented irreflexive (reflexive) chromatic number.

A broadcast is a function $f:V \rightarrow { 0,...,diam(G)}$ that assigns an integer value to each vertex such that, for each $v\in V$, $f(v)\leq e(v)$, the eccentricity of $v$. The broadcast number of a graph is the minimum value of $\sum_{v\in V}f(v)$ among all broadcasts $f$ for which each vertex of the graph is within distance $f(v)$ from some vertex $v$ having $f(v)\geq1$. This number is bounded above by the radius of the graph, as well as by its domination number. Graphs for which the broadcast number is equal to the radius are called radial. We prove a new upper bound on the broadcast number of a graph and motivate the study of radial trees by proving a relationship between the broadcast number of a graph and those of its spanning subtrees. We describe some classes of radial trees and then provide a characterization of radial trees, as well as a geometric interpretation of our characterization.

Let $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$ denote the Cartesian product of the graphs $G$ and $H$. Domination of the Cartesian product of two graphs has received much attention, with a main objective to confirm the truth of Vizing's well-known conjecture. The conjecture states that the domination number of the Cartesian product of two graphs is at least as large as the product of the respective domination numbers. The potential truth of Vizing's conjecture gives rise to investigating the domination of graph products that generalizes the Cartesian product. The generalized prism $\pi G$ of $G$ is the graph consisting of two copies of $G$, with edges between the copies determined by a permutation $\pi$ acting on the vertices of $G$. A generalized Cartesian product $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H$ is defined here, incorporating structural properties of both the Cartesian product of two graphs as well as the generalized prism of a graph. Conditions on the isomorphism of two generalized Cartesian products are explored first, establishing a characterization in the case of natural isomorphisms. A comparison of the diameter of the generalized Cartesian product and the corresponding Cartesian product graph is used to illustrate the structural differences between these graph products. This comparison is continued through a study of the validity of an inequality similar to Vizing's conjecture for Cartesian products. Graphs that attain equality in the general bounds for the domination number of the Cartesian product and generalized Cartesian product are investigated in more detail. For any graph $G$ and $n\geq 2$, $\min\{|V(G)|,\gamma(G)+n-2\}\leq\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} K_{n})\leq n\gamma(G)$. A graph $G$ is called a consistent Cartesian fixer if $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} K_{n})=\gamma(G)+n-2$ for each $n$ such that $2\leq n<|V(G)|-\gamma(G)+2$. A graph attaining equality in the stated upper bound on $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} K_{n})$ is called a Cartesian $n$-multiplier. Both of these classes are characterized. Concerning the generalized Cartesian product, $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} K_{n})\leq n\gamma(G)$ for any graph $G$, permutation $\pi$ and $n\geq 2$. A graph attaining equality in the upper bound for all $\pi$ is called a universal multiplier. Such graphs are characterized similar to a known result for generalized prisms. A similar problem for the product $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} C_{n}$ is considered, with conditions on a graph being a so-called cycle multiplier provided. A graph attaining equality in the lower bound $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H)\geq\gamma(G)$ for some permutation $\pi$ is called a $\pi$-$H$-fixer. A brief investigation is conducted into the existence of universal $H$-fixers, i.e.~graphs that are $\pi$-$H$-fixers for some $H$ and all permuations $\pi$ of $V(G)$, and it is shown that no such graphs exist when $n\geq 3$. A known efficient algorithm for determining $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} P_{n})$ is surveyed, and modified to accommodate any Cartesian product $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$, thereby establishing a general framework for evaluating the domination number of $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$ for a fixed graph $G$ and any $H$. An algorithm to determine $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} T)$ for any tree $T$ is provided, and it is observed to be polynomial for trees of bounded maximum degree. The general framework for $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$ is also modified to accommodate the generalized Cartesian product $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H$. The study diverts from the main topic of domination to investigate the planarity of the generalized Cartesian product graph. If both $G$ and $H$ are 2-connected graphs, then $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H$ is nonplanar. A known simple polynomial-time planarity testing algorithm is surveyed, and used to establish conditions on the planarity of $P_{m}\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} P_{n}$, the generalized Cartesian product of two paths. This research aims to lay the foundation on which further properties of the generalized Cartesian product and further generalizations may be studied, as well as to provide various open problems to spark interest in the research area.

We study the hyperbolic dynamical systems known as Smale spaces. More specifically we investigate the C*-algebras constructed from these systems. The K group of one of these algebras has a natural ring structure arising from an asymptotically abelian property. The K groups of the other algebras are then modules over this ring. In the case of a shift of finite type we compute these structures explicitly and show that the stable and unstable algebras exhibit a certain type of duality as modules. We also investigate the Bowen measure and its stable and unstable components with respect to resolving factor maps, and prove several results about the traces that arise as integration against these measures. Specifically we show that the trace is a ring/module homomorphism into R and prove a result relating these integration traces to an asymptotic of the usual trace of an operator on a Hilbert space.