Biosensors aiming at detection of target analytes, such as proteins, microbes, virus, and toxins, are widely needed for various applications including detection of chemical and biological warfare (CBW) agents, biomedicine, environmental monitoring, and drug screening. Surface Plasmon Resonance (SPR), as a surface-sensitive analytical tool, can very sensitively respond to minute changes of refractive index occurring adjacent to a metal film, offering detection limits up to a few ppt (pg/mL). Through SPR, the process of protein adsorption may be monitored in real-time, and transduced into an SPR angle shift. This unique technique bypasses the time-consuming, labor-intensive labeling processes, such as radioisotope and fluorescence labeling. More importantly, the method avoids the modification of the biomarker’s characteristics and behaviors by labeling that often occurs in traditional biosensors. While many transducers, including SPR, offer high sensitivity, selectivity is determined by the bio-receptors. In traditional biosensors, the selectivity is provided by bio-receptors possessing highly specific binding affinity to capture target analytes, yet their use in biosensors are often limited by their relatively-weak binding affinity with analyte, non-specific adsorption, need for optimization conditions, low reproducibility, and difficulties integrating onto the surface of transducers. In order to circumvent the use of bio-receptors, the competitive adsorption of proteins, termed the Vroman effect, is utilized in this work. The Vroman effect was first reported by Vroman and Adams in 1969. The competitive adsorption targeted here occurs among different proteins competing to adsorb to a surface, when more than one type of protein is present. When lower-affinity proteins are adsorbed on the surface first, they can be displaced by higher-affinity proteins arriving at the surface at a later point in time. Moreover, only low-affinity proteins can be displaced by high-affinity proteins, typically possessing higher molecular weight, yet the reverse sequence does not occur. The SPR biosensor based on competitive adsorption is successfully demonstrated to detect fibrinogen and thyroglobulin (Tg) in undiluted human serum and copper ions in drinking water through the denatured albumin.

A community in a social network can be viewed as a structure formed by individuals who share similar interests. Not all communities are explicit; some may be hidden in a large network. Therefore, discovering these hidden communities becomes an interesting problem. Researchers from a number of fields have developed algorithms to tackle this problem.

Besides the common feature above, communities within a social network have two unique characteristics: communities are mostly small and overlapping. Unfortunately, many traditional algorithms have difficulty recognizing these small communities (often called the resolution limit problem) as well as overlapping communities.

In this work, two enhanced community detection techniques are proposed for re-working existing community detection algorithms to find small communities in social networks. One method is to modify the modularity measure within the framework of the traditional Newman-Girvan algorithm so that more small communities can be detected. The second method is to incorporate a preprocessing step into existing algorithms by changing edge weights inside communities. Both methods help improve community detection performance while maintaining or improving computational efficiency.

Let $G=(V,E)$ be a graph. A \emph{list assignment} $L$ for $G$ is a function from

$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$

with domain $V$ such that $f(v)\in L(v)$ for all vertices $v\in V$ and $f(x)\ne f(y)$

whenever $xy\in E$. If $|L(v)|=t$ for all $v\in V$ then $L$ is a $t$-\emph{list

assignment}. The graph $G$ is $t$-choosable if for every $t$-list assignment $L$

there is an $L$-coloring. The least $t$ such that $G$ is $t$-choosable is called

the list chromatic number of $G$, and is denoted by $\ch(G)$. The complete multipartite

graph with $k$ parts, each of size $s$ is denoted by $K_{s*k}$. Erd\H{o}s et al.

suggested the problem of determining $\ensuremath{\ch(K_{s*k})}$, and showed that

$\ch(K_{2*k})=k$. Alon gave bounds of the form $\Theta(k\log s)$. Kierstead proved

the exact bound $\ch(K_{3*k})=\lceil\frac{4k-1}{3}\rceil$. Here it is proved that

$\ch(K_{4*k})=\lceil\frac{3k-1}{2}\rceil$.

An online version of the list coloring problem was introduced independently by Schauz

and Zhu. It can be formulated as a game between two players, Alice and Bob. Alice

designs lists of colors for all vertices, but does not tell Bob, and is allowed to

change her mind about unrevealed colors as the game progresses. On her $i$-th turn

Alice reveals all vertices with $i$ in their list. On his $i$-th turn Bob decides,

irrevocably, which (independent set) of these vertices to color with $i$. For a

function $l$ from $V$ to the natural numbers, Bob wins the $l$-\emph{game} if

eventually he colors every vertex $v$ before $v$ has had $l(v)+1$ colors of its

list revealed by Alice; otherwise Alice wins. The graph $G$ is $l$-\emph{online

choosable} or \emph{$l$-paintable} if Bob has a strategy to win the $l$-game. If

$l(v)=t$ for all $v\in V$ and $G$ is $l$-paintable, then $G$ is t-paintable.

The \emph{online list chromatic number }of $G$ is the least $t$ such that $G$

is $t$-paintable, and is denoted by $\ensuremath{\ch^{\mathrm{OL}}(G)}$. Evidently,

$\ch^{\mathrm{OL}}(G)\geq\ch(G)$. Zhu conjectured that the gap $\ch^{\mathrm{OL}}(G)-\ch(G)$

can be arbitrarily large. However there are only a few known examples with this gap

equal to one, and none with larger gap. This conjecture is explored in this thesis.

One of the obstacles is that there are not many graphs whose exact list coloring

number is known. This is one of the motivations for establishing new cases of Erd\H{o}s'

problem. Here new examples of graphs with gap one are found, and related technical

results are developed as tools for attacking Zhu's conjecture.

The square $G^{2}$ of a graph $G$ is formed by adding edges between all vertices

at distance $2$. It was conjectured that every graph $G$ satisfies $\chi(G^{2})=\ch(G^{2})$.

This was recently disproved for specially constructed graphs. Here it is shown that

a graph arising naturally in the theory of cellular networks is also a counterexample.