Compression of vertex transitive graphs
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
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 Type:||Article (Refereed Research - C1)|
|Keywords:||compression; vertex transitive graphs|
|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%|