Neste trabalho, estudamos o problema de encontrar grafos extremais com rela c~ao a energia laplaciana sem sinal. Mais especi camente, procuramos grafos com a maior energia laplaciana sem sinal em determinadas classes. Nesse sentido, conjecturamos que o grafo unic clico conexo com a maior energia laplaciana sem sinal e o grafo formado por um tri^angulo com v ertices pendentes distribu dos balanceadamente e provamos parcialmente essa conjectura. Tal resultado foi provado tamb em para a energia laplaciana. Al em disso, conjecturamos que o grafo com a maior energia laplaciana sem sinal dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos. / In this work, we study the problem of nding extremal graphs with relation to the signless Laplacian energy. More speci cally, we look for graphs with the largest signless Laplacian energy inside certains classes. In this sense, we conjecture that the connected unicyclic graph with the largest signless Laplacian energy is the graph consisting of a triangle with balanced distributed pendent vertices and we partially prove this conjecture. This result was also proved for the Laplacian energy. Moreover we conjecture that the graph with the largest signless Laplacian energy among all graphs with n vertices is the complete split graph with a clique of [n+1/ 3] vertices and we prove this conjecture for some classes of graphs, in particular, for trees, for unicyclic and bicyclic graphs.

Neste trabalho, estudamos o problema de encontrar grafos extremais com rela c~ao a energia laplaciana sem sinal. Mais especi camente, procuramos grafos com a maior energia laplaciana sem sinal em determinadas classes. Nesse sentido, conjecturamos que o grafo unic clico conexo com a maior energia laplaciana sem sinal e o grafo formado por um tri^angulo com v ertices pendentes distribu dos balanceadamente e provamos parcialmente essa conjectura. Tal resultado foi provado tamb em para a energia laplaciana. Al em disso, conjecturamos que o grafo com a maior energia laplaciana sem sinal dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos. / In this work, we study the problem of nding extremal graphs with relation to the signless Laplacian energy. More speci cally, we look for graphs with the largest signless Laplacian energy inside certains classes. In this sense, we conjecture that the connected unicyclic graph with the largest signless Laplacian energy is the graph consisting of a triangle with balanced distributed pendent vertices and we partially prove this conjecture. This result was also proved for the Laplacian energy. Moreover we conjecture that the graph with the largest signless Laplacian energy among all graphs with n vertices is the complete split graph with a clique of [n+1/ 3] vertices and we prove this conjecture for some classes of graphs, in particular, for trees, for unicyclic and bicyclic graphs.

Neste trabalho, estudamos o problema de encontrar grafos extremais com rela c~ao a energia laplaciana sem sinal. Mais especi camente, procuramos grafos com a maior energia laplaciana sem sinal em determinadas classes. Nesse sentido, conjecturamos que o grafo unic clico conexo com a maior energia laplaciana sem sinal e o grafo formado por um tri^angulo com v ertices pendentes distribu dos balanceadamente e provamos parcialmente essa conjectura. Tal resultado foi provado tamb em para a energia laplaciana. Al em disso, conjecturamos que o grafo com a maior energia laplaciana sem sinal dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos. / In this work, we study the problem of nding extremal graphs with relation to the signless Laplacian energy. More speci cally, we look for graphs with the largest signless Laplacian energy inside certains classes. In this sense, we conjecture that the connected unicyclic graph with the largest signless Laplacian energy is the graph consisting of a triangle with balanced distributed pendent vertices and we partially prove this conjecture. This result was also proved for the Laplacian energy. Moreover we conjecture that the graph with the largest signless Laplacian energy among all graphs with n vertices is the complete split graph with a clique of [n+1/ 3] vertices and we prove this conjecture for some classes of graphs, in particular, for trees, for unicyclic and bicyclic graphs.

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:41Z No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:55Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:27:03Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Made available in DSpace on 2017-10-09T16:27:11Z (GMT). No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) Previous issue date: 2017-05-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Let G = (V, E) be a simple and undirected graph. An edge-coloring is an assignment of colors to the edges of the graph such that any two adjacent edges receive different colors. The chromatic index of a graph G is the smallest number of colors such that G has an edge-coloring. Clearly, a lower bound for the chromatic index is the degree of the vertex of higher degree, denoted by ?(G). In 1964, Vizing proved that chromatic index is ?(G) or ?(G) + 1. The Classification Problem is to determine if the chromatic index is ?(G) (Class 1 ) or if it is ?(G) + 1 (Class 2 ). Let n be number of vertices of a graph G and let m be its number of edges. We say G is overfull if m > (n-1) 2 ?(G). Every overfull graph is Class 2. A graph is subgraph-overfull if it has a subgraph with same maximum degree and it is overfull. It is well-known that every overfull and subgraph-overfull graph is Class 2. The Overfull Conjecture asserts that every graph with ?(G) > n 3 is Class 2 if and only if it is subgraph-overfull. In this work we prove the Overfull Conjecture to a particular class of graphs, known as split-comparability graphs. The Overfull Conjecture was open to this class. / Dado um grafo simples e não direcionado G = (V, E), uma coloração de arestas é uma função que atribui cores às arestas do grafo tal que todas as arestas que incidem em um mesmo vértice têm cores distintas. O índice cromático é o número mínimo de cores para obter uma coloração própria das arestas de um grafo. Um limite inferior para o índice cromático é, claramente, o grau do vértice de maior grau, denotado por ?(G). Em 1964, Vizing provou que o índice cromático ou é ?(G) ou ?(G) + 1, surgindo assim o Problema da Classificação, que consiste em determinar se o índice cromático é ?(G) (Classe 1 ) ou ?(G) + 1 (Classe 2 ). Seja n o número de vértices de um grafo G e m seu número de arestas. Dizemos que um grafo é sobrecarregado se m > (n-1) 2 ?(G). Um grafo é subgrafo-sobrecarregado se tem um subgrafo de mesmo grau máximo que é sobrecarregado. É sabido que se um grafo é sobrecarregado ou subgrafo-sobrecarregado ele é necessariamente Classe 2. A Conjectura Overfull é uma famosa conjectura de coloração de arestas e diz que um grafo com ?(G) > n 3 é Classe 2 se e somente se é subgrafo-sobrecarregado. Neste trabalho provamos a Conjectura Overfull para uma classe de grafos, a classe dos grafos split-comparabilidade. Até este momento a Conjectura Overfull estava aberta para esta classe.

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.