81 |
An Overview of the Chromatic Number of the Erdos-Renyi Random Graph: Results and TechniquesBerglund, Kenneth January 2021 (has links)
No description available.
|
82 |
Neighborhood-Restricted [≤2]-Achromatic ColoringsChandler, James D., Desormeaux, Wyatt J., Haynes, Teresa W., Hedetniemi, Stephen T. 10 July 2016 (has links)
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.
|
83 |
Bounds on the Global Offensive K-Alliance Number in GraphsChellali, Mustapha, Haynes, Teresa W., Randerath, Bert, Volkmann, Lutz 01 January 2009 (has links)
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.
|
84 |
Chromatic Polynomials for Graphs with Split VerticesAdams, Sarah E. 12 August 2020 (has links)
No description available.
|
85 |
Invariants of E-GraphsHaynes, Teresa W. 01 January 1995 (has links)
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.
|
86 |
Chromatic Number of the Alphabet Overlap Graph, <em>G</em>(2, <em>k </em>, <em>k</em>-2).Farley, Jerry Brent 15 December 2007 (has links) (PDF)
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.
|
87 |
Solving Chromatic Number with Quantum Search and Quantum CountingLutze, David 01 June 2021 (has links) (PDF)
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.
|
88 |
An electrophysiological study of chromatic processing in the human visual system. Using visual evoked potentials and electroretinograms to study cortical and retinal contributions to human trichromatic vision.Challa, Naveen K. January 2011 (has links)
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.
|
89 |
Analysis and Design of Long Haul Fiber-Optic Communication SystemsYang, Dong 08 1900 (has links)
<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)
|
90 |
Topological Approaches to Chromatic Number and Box Complex Analysis of Partition GraphsRefahi, Behnaz 26 September 2023 (has links)
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.
|
Page generated in 0.073 seconds