33 research outputs found
On a reconstruction problem
No full textAbstractThis note supplements an earlier paper of this author, in which the concept of a strong k-hypomorphism between two graphs was defined (Thatte, 1990, Sectin VI). For k=1, this is just a hypomorphism. Here it is proved that strongly k-hypomorphic graphs and strongly k-edge hypomorphic directed graphs are isomorphic if k>1
A reconstruction problem related to balance equations II: The general case
No full textAbstractA modified k-deck of a graph G, first introduced in (Krasikov and Roditty, 1987), is obtained by removing k edges of G in all possible ways, and adding k (not necessarily new) edges in all possible ways. Krasikov and Roditty asked if it was possible to construct the usual k-edge deck of a graph from its modified k-deck. In (Thatte, to appear), the author solved this problem for the case when k = 1. In this paper, the problem is completely solved for arbitrary k. The proof makes use of the k-edge version of Lovász's result and the eigenvalues of certain matrix related to the Johnson graph
A versão algorítmica do Lema Local de Lovász com aplicações a problemas de coloração de grafos
No full textThe objective of this work is to present the proof of the algorithmic version of the Lovász local lema as well as an improved version of it and apply it to problems of coloring of graphs.O objetivo deste trabalho é apresentar a demonstração da versão algorítmica do lema local de Lovász bem como uma versão melhorada do mesmo e aplicá-lo a problemas de coloração de grafos
A versão algorítmica do Lema Local de Lovász com aplicações a problemas de coloração de grafos
No full textThe objective of this work is to present the proof of the algorithmic version of the Lovász local lema as well as an improved version of it and apply it to problems of coloring of graphs.O objetivo deste trabalho é apresentar a demonstração da versão algorítmica do lema local de Lovász bem como uma versão melhorada do mesmo e aplicá-lo a problemas de coloração de grafos
On the Boolean dimension of a graph and other related parameters
No full textWe present the Boolean dimension of a graph, we relate it with the notions of
inner, geometric and symplectic dimensions, and with the rank and minrank of a
graph. We obtain an exact formula for the Boolean dimension of a tree in terms
of a certain star decomposition. We relate the Boolean dimension with the
inversion index of a tournament.Comment: 13 pages, 2 figure
A correct proof of the McMorris–Powers’ theorem on the consensus of phylogenies
No full textAbstractMcMorris and Powers proved an Arrow-type theorem on phylogenies given as collections of quartets. There is an error in one of the main lemmas used to prove this theorem. However, this lemma (and thereby the theorem) is still true, and we provide a corrected proof
Some results on the reconstruction problems. p-claw-free, chordal, and p4-reducible graphs
No full textA claw is an induced subgraph isomorphic to K-1,K-3. The claw-point is the point of degree 3 in a claw. A graph is called p-claw-free when no p-cycle has a claw-point on it. It is proved that for p greater than or equal to 4, p-claw-free graphs containing at least one chordless p-cycle are edge reconstructible. It is also proved that chordal graphs are edge reconstructible. These two results together imply the edge reconstructibility of claw-free graphs. A simple proof of vertex reconstructibility of P-4-reducible graphs is also presented. (C) 1995 John Wiley and Sons, Inc
Reconstrução por vertex-switching e problemas relacionados
No full textO objetivo deste trabalho é apresentar métodos de álgebra linear para a resolução de alguns problemas relacionados ao problema de reconstrução de grafos por vertex-switching de Stanley (1985). O Lema de Kelly é o principal resultado obtido nesta área. Os resultados apresentados nesta dissertação podem ser divididos em duas partes. Na primeira, que consiste nos capítulos 2 e 3, apresentamos alguns problemas relacionados ao problema de reconstrução de grafos por vertex-switching. Nós começamos mostrando alguns resultados para 1-vertex-switching. Posteriormente generalizamos os resultados para o switching de conjuntos de cardinalidade arbitrária. Na segunda parte, que consiste no capítulo 4, apresentamos resultados relacionados a subgrafos obtidos pela remoção de uma aresta e generalizamos alguns deles para grafos obtidos ao se remover subconjuntos de arestas de cardinalidade arbitrária.The aim of this work is to present linear algebraic methods for some problems related
to the vertex-switching reconstruction problem of Stanley (1985). Kelly’s Lemma
for vertex-switching is the main result obtained in this area. The results in this dissertation
can be divided into two parts. In the first, consisting of chapters 2 and 3, we present
some problems related to the vertex-switching reconstruction problem. We begin presenting
some results for one-vertex switching. Next we generalize the results for the
switching of sets of arbitrary cardinality. In the second part, consisting of chapter 4, we
present results related to edge-deleted subgraphs and generalize some of them for graphs
obtained by deleting edge-subsets of arbitrary cardinality.CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superio
