No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

Let G be a finite connected graph. The circularity of G has been previously defined as σ(G) = max{r ε N| G has a circular covering of r elements, each element being a closed, connected subset of G containing at least one vertex of G}. This definition is known to be equivalent to the combinatorial description, σ(G) = max{r ε N| there is an admissible map f:V(G)→A(r)}. In this thesis, co-admissible maps are introduced and the co-circularity of a graph, G, is defined as η(G) = max{n ε N| there is a co-admissible map g:V(G)→Z_n}. It is shown that σ(G) = 2η(G) or 2η(G) + 1. It is also shown that if G is a graph and g:V(G)→Z_n is a co-admissible map, then G contains a cycle, J, called a co-admissible cycle, for which g:V(J)→Z_n is also co-admissible. Necessary and sufficient conditions are given for extending a co-admissible map on a cycle of a graph to the entire graph. If G is a graph with σ(G) = r, it is shown that any suspended (v,w)-path P in G induces, under any admissible map f:V(G)→A(r), either at most four elements of Z_r or every vertex of P with valency two induces exactly two elements of Z_r not induced by any other vertex of G. Finally it is shown that if G is a planar graph and if g:V(G)→Z_n is a co-admissible map, then any planar representation of G has exactly two faces bounded by co-admissible cycles. / Doctor of Philosophy

Wireless local area networks (WLANs) have experienced tremendous growth with the proliferation of IEEE 802.11 devices in past two decades. Wireless operators are embracing WLAN for cellular offloading in every smartphone nowadays [1]. The traffic over WLAN requires significant improvement of both WLAN throughput and efficiency. To increase throughput, multiple-input and multiple-output (MU-MIMO) has been adopted in the new generation of WLAN, such as IEEE 802.11ac. MU-MIMO systems exploit the spatial separation of users to increase the network throughput. In an MU-MIMO system, efficient channel sounding is essential for achieving optimal throughput. We propose a dynamic sounding approach for MU-MIMO systems in WLANs. We analyse and show that the optimal sounding intervals exist for single user transmit beamforming (SU-TxBF) and MU-MIMO for given channel conditions. We design a low-complexity dynamic sounding approach that adjusts the sounding interval adaptively in real-time. Through our collected over-the-air channel measurements, we demonstrate significant throughput improvements using our proposed dynamic sounding algorithm while being compliant with IEEE 802.11ac standard. Subsequently, we investigate the user grouping problem of downlink WLANs with MU-MIMO. Particularly, we focus on the problem of whether SU-TxBF or MU-MIMO should be utilized, and how many and which users should be in a multi-user (MU) group. We formulate this problem for maximizing the system throughput subject to the multi-user air time fairness (MU-ATF) criterion. We show that hypergraphs provide a suitable mathematical model and effective tool for finding the optimal or close to optimal solution. We show that the optimal grouping problem can be solved efficiently for the case where only SU-TxBF and 2-user MU groups are allowed in the system. For the general case, where any number of users can be assigned to groups of different sizes, we develop an efficient graph matching algorithm (GMA) based on graph theory principles with near-optimal performance. We evaluate the proposed algorithm in terms of system throughput using an 802.11ac emulator using collected channel measurements from an indoor environment and simulated channel samples for outdoor scenarios. We show that the approximate solution, GMA, achieves at least 93% of the optimal system throughput in all considered test cases. A complementary technique for MU-MIMO is orthogonal frequency-division multiple access (OFDMA), which will be the key enabler to maximize spectrum utilization in the next generation of WLAN, IEEE 802.11ax. An unsolved problem for 802.11ax is maximizing the number of satisfied users in the OFDMA system while accommodating the different Quality of Service (QoS) levels. We evaluate the possibility of regulating QoS through prioritizing the users in OFDMA-based WLAN. We define a User Priority Scheduling (UPS) criterion that strictly guarantees service requests of the spectrum and time resources for the users with higher priorities before guaranteeing resources to those of lower priority. We develop an optimization framework to maximize the overall number of satisfied users under this strict priority constraint. A mathematical expression for user satisfaction under prioritization constraints (scheduler) is formulated first and then linearized as a mixed integer linear program that can be efficiently solved using known optimization routine. We also propose a low-complexity scheduler having comparable performance to the optimal solution in most scenarios. Simulation results show that the proposed resource allocation strategy guarantees efficient resource allocation with the user priority constraints in a dense wireless environment. In particular, we show by system simulation that the proposed low-complexity scheduler is an efficient solution in terms of (1) total throughput and network satisfaction rate (less than 10% from the upper bound), and (2) algorithm complexity (within the same magnitude order of conventional scheduling strategy. / Ph. D.

A labeling of a graph G is said to be r-distinguishing if no automorphism of G preserves all of the vertex labels. The smallest such number r for which there is an r-distinguishing labeling on G is called the distinguishing number of G. The distinguishing set of a group Gamma, D(Gamma), is the set of distinguishing numbers of graphs G in which Aut(G) = Gamma. It is shown that D(Gamma) is non-empty for any finite group Gamma. In particular, D(D_n) is found where D_n is the dihedral group with 2n elements. From there, the generalized Petersen graphs, GP(n,k), are defined and the automorphism groups and distinguishing numbers of such graphs are given. / Master of Science

Maximum G Edge-Packing (E Pack_G) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H. The problem is primarily considered for several guest graphs (stars, paths and cycles) and host graphs (arbitrary graphs, planar graphs and trees). We give polynomial-time algorithms when G is a 2-path or when H is a tree; we show the problem is NP-complete otherwise. Also, we propose straightforward greedy polynomial-time approximation algorithms which are at least 1/|E_G| optimal. / Master of Science