20 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
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
An algebraic formulation of the graph reconstruction conjecture
No full textThe graph reconstruction conjecture asserts that a finite simple graph on at least 3 vertices can be reconstructed up to isomorphism from its deck- the collection of its vertex-deleted subgraphs. Kocay’s Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph G and any finite sequence of graphs, it gives a linear constraint that every reconstruction of G must satisfy. Let ψ(n) be the number of distinct (mutually non-isomorphic) graphs on n vertices, and let d(n) be the number of distinct decks that can be constructed from these graphs. Then the difference ψ(n) − d(n) is a measure of how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture holds for n-vertex graphs if and only if ψ(n) = d(n). We give a framework based on Kocay’s lemma to study this discrepancy. We prove that if M is a matrix of covering numbers of graphs by sequences of graphs then d(n) ≥ rankR(M). In particular, all n-vertex graphs are reconstructible if one such matrix has rank ψ(n). To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix M of covering numbers satisfies d(n) = rankR(M)
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
A reconstruction problem related to balance equations
No full textAbstractA modified k-deck of a graph is obtained by removing k edges in all possible ways and adding k (not necessarily new) edges in all possible ways. Krasikov and Roditty used these decks to give an independent proof of Müller's result on the edge reconstructability of graphs. They asked if a k-edge deck could be constructed from its modified k-deck. In this paper, we solve the problem when k = 1. We also offer new proofs of Lovász's result, one describing the constructed graph explicitly (thus answering a question of Bondy), and another based on the eigenvalues of Johnson graph
