# 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 |

## 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 (Refereed Research - C1) |

Keywords: | compression; vertex transitive graphs |

Related URLs: | |

ISSN: | 0384-9864 |

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 |