No description available.

A (closed) neighborhood-restricted [≤2]-coloring of a graph G is an assignment of colors to the vertices of G such that no more than two colors are assigned in any closed neighborhood, that is, for every vertex v in G, the vertex v and its neighbors are in at most two different color classes. The [≤2]-achromatic number is defined as the maximum number of colors in any [≤2]-coloring of G. We study the [≤2]-achromatic number. In particular, we improve a known upper bound and characterize the extremal graphs for some other known bounds.

Let G = (V (G), E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆⊆ V (G) is called a global offensive k-alliance if ΙN(ν) ∩ SΙ ≥ ΙN(ν)-SΙ+k for every ν ε V (G)-S, where N(v) is the neighborhood of ν. The global offensive k-alliance number γko(G) is the minimum cardinality of a global o ensive k-alliance in G. We present di erent bounds on γko(G) in terms of order, maximum degree, independence number, chromatic number and minimum degree.

No description available.

An E-graph is constructed by replacing each edge in a core graph G with a copy of a graph H. An important property of E-graphs is that their invariant values can be determined from parameters of the original graphs G and H. We determine chromatic number, clique number, vertex and edge cover numbers, vertex and edge independence numbers, circumference, and girth of E-graphs. A characterization of hamiltonian E-graphs is also given.

A graph G(a, k, t) is called an alphabet overlap graph where a, k, and t are positive integers such that 0 ≤ t < k and the vertex set V of G is defined as, V = {v : v = (v1v2...vk); vi ∊ {1, 2, ..., a}, (1 ≤ i ≤ k)}. That is, each vertex, v, is a word of length k over an alphabet of size a. There exists an edge between two vertices u, v if and only if the last t letters in u equal the first t letters in v or the first t letters in u equal the last t letters in v. We determine the chromatic number of G(a, k, t) for all k ≥ 3, t = k − 2, and a = 2; except when k = 7, 8, 9, and 11.

This thesis presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2n/2n2(log2n)2). This is an improvement over the best known algorithm, with a run time of 2nnO(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can be framed as NP-Hard problems, so any speed-up in the solution of these problems is highly sought after. A bulk of this thesis consists of a review of the underlying principles of quantum mechanics and quantum computing, building to the Quantum Search and Quantum Counting algorithms. The review is written with the assumption that the reader has no prior knowledge on quantum computing. This culminates with a presentation of algorithms for generating the quantum circuits required to solve K-Coloring and Chromatic Number.

The work in this thesis is concerned with examining the retinal and cortical contributions to human trichromatic colour vision. Chromatic processing at the cortex level was examined using visual evoked potentials (VEPs). These responses were elicited by chromatic spot stimuli, which were manipulated in order to selectively activate the chromatic processing system. Chromatic processing at the retinal level was examined using the electroretinograms (ERGs) for which cone isolating stimuli were used to assess the nature of L and M cone inputs to cone-opponent mechanisms. The results from the VEP experiments suggest VEP morphology is dependent upon 1) chromatic and or luminance contrast content of the stimulus, 2) stimulus size, and 3) extent to which the chromatic stimulus activates either the L/M or S/(L+M) opponent mechanism. The experiments indicate that chromatic stimulation is indexed by large N1 component and small offset responses. Optimal stimulus size for chromatic isolation is 2-4 ° along L/M axes and 6° along S/(L+M) axis. From the ERG experiments, It has been shown that the low (12Hz) and high (30Hz) temporal frequency flickering stimuli can isolate the chromatic and luminance processing mechanisms in the retina. For low temporal frequency ERGs, the L:M ratio was close to unity and L/M phase difference was close to 180°. For high temporal frequency ERGs, the L:M ratio was more than unity and L/M phase difference was close to 90°. In addition to this, the variation in L:M ratio across the retinal eccentricity was also examined. These results suggest, for the chromatic processing, L:M ratio is close to unity independent of retinal eccentricity and individuals. For the luminance processing, L:M ratio is more than unity and depends upon the region of the retina being stimulated. These findings indicate the maintenance of cone selective input for the chromatic processing across the human retina.

<p> This thesis deals with the limiting factors in the design of a long-haul fiber-optic communication system, and the techniques used to suppress their resulting impairments. These limiting factors include both linear and nonlinear effects, such as fiber chromatic dispersion and the Kerr nonlinearity, and the modulator-induced nonlinearity. </p> <p> In Chapter 3, the conditional probability density function (PDF) of the received elect rical signal given transmitted bit '1 '/'0' for a coherent fiber-optic transmission system based on binary phase shift keying (BPSK) is mathematically derived. Both amplified spontaneous emission (ASE) noise and fiber nonlinearity are taken into account . The results show that the conditional PDF of given bit '1' or '0' is asymmetric when intrachannel four-wave mixing (IFWM) is dominant, while it becomes nearly symmetric when the variance of ASE is much larger than that due to IFWM. The standard deviation of the received signal is calculated analytically. The system parameters, including optimum dispersion map and pre-compensation ratio, are optimized by analytically calculating variance of IFWM. Significant computation efforts can be saved using this approach as compared to full numerical simulations of the nonlinear Schrodinger equation, without losing much accuracy. </p> <p> In Chapter 4, an improved 4-f time-lens configuration is proposed. Fourier transform (FT) and inverse Fourier transform (IFT) can be realized using time lenses such that there is no need for time reversal at the end. A typical 4-f configuration consists of two 2-f systems and a temporal filter. The first 2-f system consisting of a time lens and two dispersive elements produces the Fourier transform (FT) of the input signal. The temporal filter modifies the spectrum. The next 2-f system produces the inverse Fourier transform (IFT). A wavelength division demultiplexer and a higher-order dispersion compensator based on 4-f configuration are numerical implemented. One of the advantages of the time-lens-based temporal filtering technique is that the transfer function of the temporal filter can be dynamically altered by changing the input voltage to the temporal filter (amplitude/phase modulator) and therefore, this technique could be used for dynamic switching and multiplexing in optical networks. </p> <p> In chapter 5, a direct-detection optical orthogonal frequency division multiplexing (DD-0-0FDM) is realized using time lenses. Typically, in OFDM systems, discrete Fourier transform (DFT) is used at the transmitter and inverse discrete Fourier transform (IDFT) is used at the receiver. In this chapter, it is proposed to use continuous Fourier transform (FT) and inverse Fourier transform (IFT) using time lenses that replace DFT and IDFT in the electrical domain. The third- and higher-order dispersive effects can be considerably reduced using the proposed DD-0-0FDM scheme. </p> <p> In Chapter 6, a coherent optical orthogonal frequency division multiplexing (OFDM) (C0-0-0FDM) scheme using time lenses is analyzed. The comparison of performance between the proposed scheme and the conventional optical OFDM scheme using fast Fourier transform (FFT) and inverse FFT in the electrical domain is made. Both the Mach-Zehnder modulator (MZM) induced and fiber induced nonlinearities are investigated. Results show that the time-lens-based C0-0-0FDM performs almost the same as the FFT-based C0-0-0FDM when the message signal launched to MZM is low so that MZM operates in the linear region. The nonlinearity of MZM degrades the performance of FFT-based C0-0-0FDM drastically when the power of message signal becomes sufficiently large, but only has negligible impact on the time-lens-based C0-0-0FDM. A periodical driving voltage has been proposed to set up the time lens such that the maximally required driving voltage level is kept low within the time frame. The advantages using the time-lens-based C0-0-0FDM are that (i) FT can be done in optical domain almost instantaneously, whereas the FFT in digital domain is slow and requires significant computational efforts, (ii) optical domain Fourier transform has a large bandwidth (~THz) and therefore, FT /IFT can be performed at a large symbol rate. </p> <p> In Chapter 7, the digital backward propagation (DBP) has been studied both in orthogonal frequency-division multiplexing ( OFDM) and single-carrier (SC) fiber-optic transmission systems. 16 quadrature amplitude modulation (QAM) is used for both systems with the bit rate of 100 Gbjs. The results show that OFDM and SC with Nyquist pulses (SC-Nyquist) have a superior performance as compared to SC with raisedcosine pulses (SC-NRZ) when the DBP is used. The impact of electrical filter bandwidth and nonlinear phase/amplitude noise has also been investigated. The performance of perfect-BP-based OFDM/SC initially improves when the electrical filter bandwidth increases at high signal-to-noise ratio (SNR). The comparison of the effects of nonlinear phase/amplitude noise among OFDM, SC-Nyquist and SC-NRZ systems is made and it is shown that SC-NRZ systems significantly suffer from the effects of nonlinear phase/amplitude noise, which explains the performance advantage of OFDM/SC-Nyquist over SC-NRZ when the DBP used. </p> / Thesis / Doctor of Philosophy (PhD)

Determining the chromatic number of the partition graph P(33) poses a considerable challenge. We can bound it to 4 ≤ χ(P(33)) ≤ 6, with exhaustive search confirming χ(P(33)) = 6. A potential mathematical proof strategy for this equality involves identifying a Z2-invariant S4 with non-trivial homology in the box complex of the partition graph P(33), namely Bedge(︁P(33))︁, and applying the Borsuk-Ulam theorem to compute its Z2-index. This provides a robust topological lower bound for the chromatic number of P(33), termed the Lovász bound. We have verified the absence of such an S4 within certain sections of Bedge(︁P(33))︁. We also validated this approach through a case study on the Petersen graph. This thesis offers a thorough examination of various topological lower bounds for a graph’s chromatic number, complete with proofs and examples. We demonstrate instances where these lower bounds converge to a single value and others where they diverge significantly from a graph’s actual chromatic number. We also classify all vertex pairs, triples, and quadruples of P(33) into unique equivalence classes, facilitating the derivation of all maximal complete bipartite subgraphs. This classification informs the construction of all simplices of Bedge(︁P(33)). Following a detailed and technical exploration, we uncover both the maximal size of the pairwise intersections of its maximal simplices and their underlying structure. Our study proposes an algorithm for building the box complex of the partition graph P(33) using our method of identifying maximal complete bipartite subgraphs. This reduces time complexity to O(n3), marking a substantial enhancement over brute-force techniques. Lastly, we apply discrete Morse theory to construct a simplicial complex homotopy equivalent to the box complex of P(33), using two methods: elementary collapses and the determination of a discrete Morse function on the box complex. This process reduces the dimension of the box complex from 35 to 12, streamlining future calculations of the Z2-index and the Lovász bound.