Página 1 dos resultados de 22773 itens digitais encontrados em 0.048 segundos

In search of a poset structure to the regular exceptional graphs

Barbedo, Inês; Cardoso, Domingos M.; Rama, Paula
Fonte: Instituto Politécnico de Bragança Publicador: Instituto Politécnico de Bragança
Tipo: Conferência ou Objeto de Conferência
Português
Relevância na Pesquisa
36.6068%
A (k,t)-regular set is a subset of the vertices of a graph, inducing a k -regular subgraph such that every vertex not in the subset has t neighbors in it. An exceptional graph is a connected graph with least eigenvalue greater than or equal to -2 which is not a generalized line graph, and it is shown that the set of regular exceptional graphs is partitioned in three layers. The idea of a recursive construction of regular exceptional graphs is proposed in [1]. With a new technique we prove that all regular exceptional graphs from the 1st and 2nd layer could be produced by this technique. The new recursive technique is based on the construction of families of regular graphs, where each regular graph is obtained by a (k,t)-extension defined by a k- regular graph H such that V(H) is a (k,t)-regular set of the extended regular graph. The process of extending a graph is reduced to the construction of the incidence matrix of a combinatorial 1-design, and these extensions induce a partial order. Considering several rules to reduce the production of isomorphic graphs, each exceptional regular graph is constructed by a (0,2)-extension. Based on this construction, an algorithm to produce the regular exceptional graphs of the 1st and 2nd layer is introduced and the corresponding poset is presented...

The construction of the poset of regular execeptional graphs using equitable partitions

Barbedo, Inês; Cardoso, Domingos M.; Rama, Paula
Fonte: Instituto Politécnico de Bragança Publicador: Instituto Politécnico de Bragança
Tipo: Conferência ou Objeto de Conferência
Português
Relevância na Pesquisa
36.63043%
An exceptional graph is a connected graph with least eigenvalue greater than or equal to -2 which is not a generalized line graph. It is shown that the set of regular exceptional graphs is partitioned in three layers. A (k,t)-regular set is a subset of the vertices of a graph, inducing a k-regular subgraph such that every vertex not in the subset has t neighbors in it. A new recursive construction of regular exceptional graphs is proposed, where each regular exceptional graph of the first and the second layer is constructed by a (0,2)-regular set extension. In this talk we present an algorithm based on this recursive construction and show that this technique induces a partial order relation on the set of regular exceptional graphs. The process of extending a graph is reduced to the construction of the incidence matrix of a combinatorial 1-design, considering several rules to prevent the production of isomorphic graphs, and we show that each regular exceptional graph has an equitable partition which, by this construction technique, is extended with a new element, the set of the additional vertices. The recursive construction is generalized to the construction of arbitrary families of regular graphs, by extending a regular graph G with another regular graph H such that V(H) is a (k...

The poset structure of the regular exceptional graphs

Barbedo, Inês; Cardoso, Domingos M.; Rama, Paula
Fonte: Instituto Politécnico de Bragança Publicador: Instituto Politécnico de Bragança
Tipo: Conferência ou Objeto de Conferência
Português
Relevância na Pesquisa
36.63043%
An exceptional graph is a connected graph with least eigenvalue greater than or equal to -2 which is not a generalized line graph. It is shown that the set of regular exceptional graphs is partitioned in three layers. A (k,t)-regular set is a subset of the vertices of a graph, inducing a k-regular subgraph such that every vertex not in the subset has t neighbors in it. A new recursive construction of regular exceptional graphs is proposed, where each exceptional regular graph is constructed by a (0,2)-regular set extension. These extensions induce a partial order on the set on the exceptional graphs in each layer. Based on this construction, an algorithm to produce the regular exceptional graphs of the first and second layer is introduced and the corresponding poset is presented, using its Hasse diagram. The process of extending a graph is reduced to the construction of the incidence matrix of a combinatorial 1-design, considering several rules to prevent the production of isomorphic graphs. A generalization of this recursive procedure to the construction of families of regular graphs, where each regular graph is obtained by a (k,t)-regular extension defined by a k-regular graph H such that V(H) is a (k,t)-regular set of the extended regular graph...

Sparse partition universal graphs for graphs of bounded degree

KOHAYAKAWA, Yoshiharu; ROEDL, Vojtech; SCHACHT, Mathias; SZEMEREDI, Endre
Fonte: ACADEMIC PRESS INC ELSEVIER SCIENCE Publicador: ACADEMIC PRESS INC ELSEVIER SCIENCE
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
36.6068%
In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.; CAPES-DAAD; DAAD; Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES); FAPESP; Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP); CNPq[FAPESP 2003/09925-5]; Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq); Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq); CNPq[308509/2007-2]; Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq); CNPq[485671/2007-7]; Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq); CNPq[486124/2007-0]; Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq); CNPq[484154/2010-9]; NSF; NSF[DMS 0300529]; NSF[DMS 0800070]; NSF; NSF[DMS 0100784]; NSF; NSF; NSF[DMS 0603745]

UNIVERSALITY OF RANDOM GRAPHS

Dellamonica, Domingos, Jr.; Kohayakawa, Yoshiharu; Roedl, Vojtech; Rucinski, Andrzej
Fonte: SIAM PUBLICATIONS; PHILADELPHIA Publicador: SIAM PUBLICATIONS; PHILADELPHIA
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
36.6068%
We prove that asymptotically (as n -> infinity) almost all graphs with n vertices and C(d)n(2-1/2d) log(1/d) n edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.; CAPES; NSF [DMS080070]; Charles University, Prague; FAPESP [FAPESP 2003/09925-5]; CNPq [308509/2007-2, 485671/2007-7, 486124/2007-0]; Polish Ministry of Higher Education [N201036 32/2546]

Caminhos mais longos em grafos; Longest paths in graphs

De Rezende, Susanna Figueiredo
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 30/05/2014 Português
Relevância na Pesquisa
36.64984%
O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente...

Sobre a coloração total semiforte; On the adjacent-vertex-distinguishing-total colouring of graphs

Atílio Gomes Luiz
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 28/04/2014 Português
Relevância na Pesquisa
36.679836%
O problema da coloração total semiforte foi introduzido por Zhang et al. por volta de 2005. Este problema consiste em associar cores às arestas e aos vértices de um grafo G=(V(G),E(G)), utilizando o menor número de cores possível, de forma que: (i) quaisquer dois vértices ou duas arestas adjacentes possuam cores distintas; (ii) cada vértice tenha cor diferente das cores das arestas que nele incidem; e, além disso, (iii) para quaisquer dois vértices adjacentes u,v pertencentes a V(G), o conjunto das cores que colorem u e suas arestas incidentes é distinto do conjunto das cores que colorem v e suas arestas incidentes. Denominamos esse menor número de cores para o qual um grafo admite uma coloração total semiforte como número cromático total semiforte. Zhang et al. também determinaram o número cromático total semiforte de algumas famílias clássicas de grafos e observaram que todas elas possuem uma coloração total semiforte com no máximo Delta(G)+3 cores. Com base nesta observação, eles conjeturaram que Delta(G)+3 cores seriam suficientes para construir uma coloração total semiforte para qualquer grafo simples G. Essa conjetura é denominada Conjetura da Coloração Total Semiforte e permanece aberta para grafos arbitrários...

Edge-clique graphs and the lambda-coloring problem

Calamoneri,Tiziana; Petreschi,Rossella
Fonte: Sociedade Brasileira de Computação Publicador: Sociedade Brasileira de Computação
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/01/2001 Português
Relevância na Pesquisa
36.64984%
This paper deals with edge-clique graphs and with the lambda-coloring problem when restricted to this class. A characterization of edge-clique graphs of out-erplanar graphs is given; a complete description of edge-clique graphs of threshold graphs is presented and a linear time algorithm for lambda-coloring the edge-clique graph of a threshold graph is provided. A survey on the lambda-coloring problem, when restricted to edge-clique graphs, is reported.

Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic Graphs

Salarinezhad, Asefeh
Fonte: Brock University Publicador: Brock University
Tipo: Electronic Thesis or Dissertation
Português
Relevância na Pesquisa
36.63043%
In this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from Merriam-Webster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.

Distance and symmetry properties of graphs and their application to interconnection networks and codes; Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos

Camarero Coterillo, Cristobal
Fonte: Universidade de Cantabria Publicador: Universidade de Cantabria
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
36.64984%
ABSTRACT: The topology of a interconnection network is the graph of its routers. The topologies that are being currently used in large supercomputers can be classified into two families: the ones that use routers with moderate radix and the ones using high-radix routers. The objective of this thesis is to define topologies for both families that exhibit better properties than the actual ones. Examples of moderate degree machines are the Cray XK7, the K computer and the Blue Gene/Q, whose topologies are tori. In this thesis the lattice graphs are proposed. They are variant of tori with reduced distances and which can be symmetric for sizes in which the tori is forced to be asymmetric. Among the most used topologies for the family of high-radix routers there are the Clos networks, and more recently, the dragonfly networks. This thesis focuses on dragonfly networks. In this thesis, it is explained how Hamming graphs can be seen as a dragonfly with large global trunking and that some properties of the Hamming graphs can be extrapolated to dragonflies. The problem of finding lattice graphs with optimal distance properties is actually equivalent to the problem of finding good codes over the Lee space. In this thesis several quasi-perfect codes are built...

Gromov hiperbolicity in graphs

Carballosa Torres, Walter
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
36.64984%
If X is a geodesic metric space and x1, x2, x3 ∈ X, a geodesic triangle T = {x1, x2, x3} is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in the δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) := inf{δ ≥ 0 : X is δ-hyperbolic } . The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. One of the main aims of this PhD Thesis is to obtain quantitative information about the distortion of the hyperbolicity constant of the graph G e obtained from the graph G by deleting an arbitrary edge e from it. These inequalities allow to obtain other main result, which characterizes in a quantitative way the hyperbolicity of any graph in terms of local hyperbolicity. In this work we also obtain information about the hyperbolicity constant of the line graph L(G) in terms of properties of the graph G. In particular, we prove qualitative results as the following: a graph G is hyperbolic if and only if L(G) is hyperbolic; if {Gn} is a T-decomposition of G ({Gn} are simple subgraphs of G)...

Alliance polynomial and hyperbolicity in regular graphs

Torres Núñez, Yadira
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
36.725986%
One of the open problems in graph theory is the characterization of any graph by a polynomial. Research in this area has been largely driven by the advantages offered by the use of computers which make working with graphs: it is simpler to represent a graph by a polynomial (a vector) that by the adjacency matrix (a matrix). We introduce the alliance polynomial of a graph. The alliance polynomial of a graph G with order n and maximum degree δ_1 is the polynomial A(G; x) = ∑_(k=〖-δ〗_1)^(δ_1)▒〖Ak(G) x^(n+k) 〗, where A{_k}(G) is the number of exact defensive k-alliances in G. Also, we develop and implement an algorithm that computes in an efficient way the alliance polynomial. We obtain some properties of A(G; x) and its coefficients for: • Path, cycle, complete and star graphs. In particular, we prove that they are characterized by their alliance polynomials. • Cubic graphs (graphs with all of their vertices of degree 3), since they are a very interesting class of graphs with many applications. We prove that they verify unimodality. Also, we compute the alliance polynomial for cubic graphs of small order, which satisfy uniqueness. • Regular graphs (graphs with the same degree for all vertices). In particular...

Problemas em grafos com poucos P4's em grafos indiferença; Problems on graphs with few P4's and indifference graphs

Vagner Pedrotti
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 19/08/2011 Português
Relevância na Pesquisa
36.738047%
Nesta tese de doutoramento sáo considerados três problemas em grafos, para os quais sáo obtidos resultados quando a entrada é restrita a algumas classes. Todos os problemas sáo problemas de otimização combinatória sobre grafos simples e apresentam diferentes classificações de complexidade. Em dois casos, o estudo focou classes de grafos com "poucos iYs" e ° uso da decomposição modular. No último caso, considerou-se uma subclasse dos grafos de intervalos e a aplicação de uma técnica conhecida como pullback. O primeiro problema estudado é o Problema dos Separadores Minimais, para o qual são conhecidos algoritmos polinomiais em toda classe de grafos que possuir um número polinomial de separadores minimais. Serão dados, como contribuição deste trabalho, um algoritmo linear para listar os separadores minimais de grafos P4-carregados estendidos e limitantes justos no número e tamanho dos separadores minimais destes grafos, bem como de algumas de suas subclasses, P4-carregada, P4-arrumada e P4-íeve. Estes resultados estendem um algoritmo anterior para grafos P4-esparsos, ao mesmo tempo que incluem estas classes de grafos entre as que possuem um número de separadores minimais limitado por um função linear no número de vértices do grafo. Em seguida...

Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König; On structural characterizations of graph classes related to perfect graphs and the König property

Safe, Martín Darío
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: info:eu-repo/semantics/doctoralThesis; tesis doctoral; info:eu-repo/semantics/publishedVersion Formato: application/pdf
Publicado em //2011 Português
Relevância na Pesquisa
36.738047%
Un grafo es balanceado si su matriz clique no contiene como submatriz ninguna matriz de incidencia arista-vértice de un ciclo impar. Se conoce una caracterización para estos grafos por subgrafos inducidos prohibidos, pero ninguna que sea por subgrafos inducidos prohibidos minimales. En esta tesis probamos caracterizaciones por subgrafos inducidos prohibidos minimales para los grafos balanceados restringidas a ciertas clases de grafos y mostramos que dentro de algunas de ellas conducen a algoritmos lineales para reconocer el balanceo. Un grafo es clique-perfecto si en cada subgrafo inducido el mínimo número de vértices que intersecan todas las cliques coincide con el máximo número de cliques disjuntas dos a dos. Contrariamente a los grafos perfectos, para estos grafos no se conoce una caracterización por subgrafos inducidos prohibidos ni la complejidad del problema de reconocimiento. En esta tesis caracterizamos los grafos clique-perfectos por subgrafos inducidos prohibidos dentro de dos clases de grafos, lo que implica algoritmos de reconocimiento polinomiales para la clique-perfección dentro de dichas clases. Un grafo tiene la propiedad de Kőnig si el mínimo número de vértices que intersecan todas las aristas iguala al máximo número de aristas que no comparten vértices. En esta tesis caracterizamos estos grafos por subgrafos prohibidos...

Caracterizaciones estructurales de grafos de intersección; Structural characterizations of intersection graphs

Grippo, Luciano Norberto
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: info:eu-repo/semantics/doctoralThesis; tesis doctoral; info:eu-repo/semantics/publishedVersion Formato: application/pdf
Publicado em //2011 Português
Relevância na Pesquisa
36.76919%
En esta tesis estudiamos caracterizaciones estructurales para grafos arcocirculares, grafos circulo, grafos probe de intervalos, grafos probe de interva 10s unitarios, grafos probe de bloques y grafos probe co-bipartitos. Un grafo es arc0 circular (circulo) si es el grafo de interseccion de una familia de arcos (cuerdas) en una circunferencia. Dada una familia hereditaria de grafos G, un grafo es probe G si sus vertices pueden particionarse en dos conjuntos: un conjunto de vertices probe y un conjunto de vertices nonprobe, de forma tal que el conjunto de vertices nonprobe es un conjunto independiente y es posible obtener un grafo en la clase G agregando aristas entre ellos. Los grafos probe G forman una superclase de la familia G. Por lo tanto, 10s grafos probe de intervalos y 10s grafos probe de intervalos unitarios generalizan la clase de 10s grafos de intervalos y 10s grafos de intervalos unitarios respectivamente. Caracterizamos parcialmente a 10s grafos arco-circulares, grafos circulo, grafos probe de intervalos y probe de interval0 unitario mediante subgrafos prohibidos dentro de ciertas familias hereditarias de grafos. Finalmente, es presentada una caracterizacion de 10s grafos probe co-bipartitos que lleva a un algoritmo de reconocimiento de tiempo polinomial para dicha clase y 10s grafos probe de bloques son caracterizados mediante una lista de subgrafos prohibidos.; In this Thesis we study structural characterizations for six classes of graphs...

Coordinated graphs and clique graphs of clique-Helly perfect graphs

Durán, Guillermo; Groshaus, Marina; Bonomo, Flavia
Fonte: Universidade do Chile Publicador: Universidade do Chile
Tipo: Artículo de revista
Português
Relevância na Pesquisa
36.701938%
Publicación ISI; A new class of graphs related to perfect graphs is defined in this work: coordinated graphs. A graph G is coordinated if the cardinality of a maximum set of cliques of H with a common vertex is equal to the cardinality of a minimum partition of the cliques of H into clique-independent sets, for every induced subgraph H of G. A graph G is K-perfect when its clique graph K(G) is perfect. The concept of special clique subgraph is defined, which leads us to the notion of c-coordinated graphs (coordination relative to these clique subgraphs). We prove that coordinated graphs are a subclass of perfect graphs and relate K-perfect graphs with c-coordinated graphs. Finally, clique graphs of clique-Helly and hereditary clique Helly perfect graphs are analyzed.

Structural results on circular-arc graphs and circle graphs: A survey and the main open problems

Grippo, Luciano N.; Safe, Martín D.; Durán, Guillermo Alfredo
Fonte: Elsevier Publicador: Elsevier
Tipo: Artículo de revista
Português
Relevância na Pesquisa
36.666067%
Artículo de publicación ISI; Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are the intersection graphs of chords on a circle. These graph classes have been the subject of much study for many years and numerous interesting results have been reported. Many subclasses of both circular-arc graphs and circle graphs have been defined and different characterizations formulated. In this survey, we summarize the most important structural results related to circular-arc graphs and circle graphs and present the main open problems.; The first author was partially supported by FONDECyT Grant 1110797 and Millennium Science Institute ‘‘Complex Engineering Systems’’ (Chile). All the authors were partially supported by ANPCyT PICT-2007-00518, UBACyT Grant 20020090300094 and CONICET PIP 112-200901-00160 (Argentina).

On minimal forbidden subgraph characterizations of balanced graphs

Safe, Martín D.; Wagler, Annegret K.; Durán, Guillermo Alfredo; Bonomo, Flavia
Fonte: Universidade do Chile Publicador: Universidade do Chile
Tipo: Artículo de revista
Português
Relevância na Pesquisa
36.63043%
Artículo de publicación ISI; A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work,we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.

Graph coloring heuristics from investigation of smallest hard to color graphs

Radin, Andrew
Fonte: Rochester Instituto de Tecnologia Publicador: Rochester Instituto de Tecnologia
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
36.63043%
Vertex coloring of graphs is an NP-complete problem. No polynomial time algorithm is known to color graphs optimally. The best we can do to handle vertex coloring of graphs is to create heuristics which provide a guess as to an optimal coloring. This thesis examines a number of known vertex coloring heuristics, and compares their performance to a brute-force optimal coloring. These comparisons are made for relatively small graphs with low numbers of vertices. The behaviors of the existing heuristics is examined to aid in the creation of new heuristics. The new heuristics are compared against the existing heuristics for both all small (n < 12) and relatively large random graphs. The result of this thesis is two new graph coloring heuristics. The first heuristic, the so called double interchange, provides the best coloring performance of the heuristics studied for small, connected graphs. The second heuristic, the annealing interchange, provides the best coloring performance of the heuristics studied for larger, random graphs.

Strongly regular graphs, association schemes and Gauss sums

Wu, Fan
Fonte: University of Delaware Publicador: University of Delaware
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
36.63043%
Xiang, Qing; Gauss sums play an important role in the construction of strongly regular Cayley graphs and association schemes. Compared with other approaches to the constructions of strongly regular graphs, the method using Gauss sums requires a lot of background knowledge from algebra and number theory. In [50], Schmidt and White provided a conjecture on cyclotomic strongly regular graphs which contains 11 sporadic examples of cyclotomic strongly regular graphs. We rst generalize one of their sporadic examples to an innite family of strongly regular graphs by using a union of cyclotomic classes. We do so by rst deriving expressions for the (restricted) eigenvalues of Cayley graphs without evaluating Gauss sums explicitly, and then giving conditions that determined candidate Cayley graphs be strongly regular. A. V. Ivanov's conjecture on amorphic association schemes was rst disproved by Van Dam. Before the work of this dissertation, only nitely many counterexamples were known. In the dissertation, we shall give 15 innite families of counter examples to Ivanov's conjecture. Moreover, our families of association schemes are pseudocyclic. We shall prove this fact by using the properties of Gauss sums of the index 2.; University of Delaware...