Litow, Bruce, Deo, Narsingh, and Cami, Aurel (2004) Compression of vertex transitive graphs. Congressus Numerantium, 167. pp. 161-173.

PDF (Published Version) Restricted to Repository staff only

Abstract

We consider the lossless compression of vertex transitive graphs. An undirected graph G = (V, E) is called vertex transitive if for every pair of vertices x, y ∈ V , there is an automorphism σ of G, such that σ(x) = y. A result due to Sabidussi, guarantees that for every vertex transitive graph G there exists a graph mG (m is a positive integer) which is a Cayley graph. We propose as the compressed form of G a finite presentation (X, R) , where (X, R) presents the group Γ corresponding to such a Cayley graph mG. On a conjecture, we demonstrate that for a large subfamily of vertex transitive graphs, the original graph G can be completely reconstructed from its compressed representation.

Item ID:	6117
Item Type:	Article (Research - C1)
ISSN:	0384-9864
Keywords:	compression; vertex transitive graphs
Related URLs:	Publisher
Date Deposited:	08 Jan 2010 02:04
FoR Codes:	08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080201 Analysis of Algorithms and Complexity @ 100%
SEO Codes:	89 INFORMATION AND COMMUNICATION SERVICES > 8999 Other Information and Communication Services > 899999 Information and Communication Services not elsewhere classified @ 100%
Downloads:	Total: 1
	More Statistics