During the past few decades, examinations of social, biological, and communication networks have taken on increased attention. While numerous models of these networks have arisen, some have lacked visual representations. This is particularly true in ecology, where scientists have often been restricted to at most three dimensions when creating graphical representations of pattern and process. I will introduce an application of dot product representation graphs that allows scientists to view the high dimensional connections in ecological networks. Using actual data, example graphs will be developed and analyzed using key measures of graph theory.

We will introduce three new classes of graphs; namely bipartite dot product graphs, probe dot product graphs, and combinatorial orthogonal graphs. All of these representations were inspired by a vector representation known as a dot product representation. Given a bipartite graph G = (X, Y, E), the bipartite dot product representation of G is a function ƒ : X ∪ Y → Rk and a positive threshold t such that for any κ ∈ Χ and γ ∈ Υ , κγ ∈ ε if and only if f(κ) · f(γ) ≥ t. The minimum k such that a bipartite dot product representation exists for G is the bipartite dot product dimension of G, denoted bdp(G). We will show that such representations exist for all bipartite graphs as well as give an upper bound for the bipartite dot product dimension of any graph. We will also characterize the bipartite graphs of bipartite dot product dimension 1 by their forbidden subgraphs. An undirected graph G = (V, E) is a probe C graph if its vertex set can be parti-tioned into two sets, N (nonprobes) and P (probes) where N is independent and there exists E' ⊆ N × N such that G' = (V, E ∪ E) is a C graph. In this dissertation we introduce probe k-dot product graphs and characterize (at least partially) probe 1-dot product graphs in terms of forbidden subgraphs and certain 2-SAT formulas. These characterizations are given for the very different circumstances: when the partition into probes and nonprobes is given, and when the partition is not given. Vectors κ = (κ1, κ2, . . . , κn)T and γ = (γ1, γ2, . . . , γn)T are combinatorially orthogonal if |{i : κiγi = 0}| ≠ 1. An undirected graph G = (V, E) is a combinatorial orthogonal graph if there exists ƒ : V → Rn for some n ∈ Ν such that for any u, υ &Isin; V , uv ∉ E iff ƒ(u) and ƒ(v) are combinatorially orthogonal. These representations can also be limited to a mapping g : V → {0, 1}n such that for any u,v ∈ V , uv ∉ E iff g(u) · g(v) = 1. We will show that every graph has a combinatorial orthogonal representation. We will also state the minimum dimension necessary to generate such a representation for specific classes of graphs.

The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.

Submitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2016-03-04T16:57:18Z No. of bitstreams: 2 Tese - Leila Roling Scariot da Silva - 2015.pdf: 821704 bytes, checksum: afe6afd0f3cea67708178512b59c2c09 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-03-07T12:10:47Z (GMT) No. of bitstreams: 2 Tese - Leila Roling Scariot da Silva - 2015.pdf: 821704 bytes, checksum: afe6afd0f3cea67708178512b59c2c09 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-07T12:10:47Z (GMT). No. of bitstreams: 2 Tese - Leila Roling Scariot da Silva - 2015.pdf: 821704 bytes, checksum: afe6afd0f3cea67708178512b59c2c09 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-10-30 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / Given a graph G, a defensive alliance of a set of vertices A⊆V(G) satisfying the condition that for each v ∈ A, |N[v] ∩ A| ≤ |N[v] − A|. The set S is an offensive alliance if the inaquality holds for every v ∈ N[S]−S. A alliance A is called global if is also a dominant set. In this paper, we establish lower bounds for Simplicial Graphs and further give closed formulas and upper bounds to decide the global, defensive, offensive, alliance numbers for lexicographic product of paths, cycles, stars and complete graphs. We establish a relationship to global defensive alliance numbers and complementary prism product to graphs. / A aliança é um conceito introduzido por Hedetniemi, Hedetniemi e Kristiansen em 2004, onde foram classificadas em defensiva, ofensiva ou poderosa. Informalmente, podemos entender uma aliança como uma coleção de entidades tal que a união é mais forte do que o indivíduo. Uma aliança, de qualquer entidade, pode tanto servir para proteção contra ataques, quanto para aumentar a capacidade para atacar outras entidades. Toda aliança é global se for um conjunto dominante. A complexidade computacional e aplicações para a defesa nacional, redes de computadores, distribuição computacional e redes sociais são exemplos que motivam os estudos sobre alianças em grafos. Neste trabalho nós lidamos com alguns limites e fórmulas fechadas de algumas famílias de produto lexicográfico para obter o número mínimo da aliança defensiva global e aliança ofensiva global e apresentamos uma relação entre grafos gerais e sua aliança defensiva global para prisma complementar, bem como obtivemos limites para algumas famílias de grafos como grafos simplicias.

A k-king in a digraph D is a vertex that can reach every other vertex in D by a directed path of length at most k. A king is a vertex that is a k-king for some k. We will look at kings in the direct product of digraphs and characterize a relationship between kings in the product and kings in the factors. This is a continuation of a project in which a similar characterization is found for the cartesian product of digraphs, the strong product of digraphs, and the lexicographic product of digraphs.

This thesis touches three different topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices is connected by atleast one path in which no two edges are coloured the same. The rainbow connection number of a graph is the minimum number of colours required to rainbow colour it. In this thesis we give upper bounds on rainbow connection number based on graph invariants like minimum degree, vertex connectivity, and radius. We also give some computational complexity results for special graph classes. Product dimension The product dimension or Prague dimension of a graph G is the smallest natural number k such that G is an induced subgraph of a direct product of k complete graphs. In this thesis, we give upper bounds on the product dimension for forests, bounded tree width graphs and graphs of bounded degeneracy. Boxicity and cubicity The boxicity (cubicity of a graph G is the smallest natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes(axis-parallel unit cubes) in Rk .In this thesis, we study the boxicity and the cubicity of Cartesian, strong and direct products of graphs and give estimates on the boxicity and the cubicity of a product graph based on invariants of the component graphs. Separation dimension The separation dimension of a hypergraph H is the smallest natural number k for which the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyper plane normal to one of the axes. While studying the boxicity of line graphs, we noticed that a box representation of the line graph of a hypergraph has a nice geometric interpretation. Hence we introduced this new parameter and did an extensive study of the same.