Fault tolerant supergraphs with automorphisms

DOI10.1016/J.DAM.2018.06.012MaRDI QIDQ1720338zbMATH OpenOpenAlexFDO

Authors Ashwin Ganesan

Publication date 8 February 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.04855

zbMATH Keywords

interconnection networksgraph automorphismspermutation groupsfault-tolerant system designstructural fault tolerance

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (05C99)

Abstract: Given a graph $Y$ on $n$ vertices and a desired level of fault-tolerance $k$, an objective in fault-tolerant system design is to construct a supergraph $X$ on $n+k$ vertices such that the removal of any $k$ nodes from $X$ leaves a graph containing $Y$. In order to reconfigure around faults when they occur, it is also required that any two subsets of $k$ nodes of $X$ are in the same orbit of the action of its automorphism group. In this paper, we prove that such a supergraph must be the complete graph. This implies that it is very expensive to have an interconnection network which is $k$-fault-tolerant and which also supports automorphic reconfiguration. Our work resolves an open problem in the literature. The proof uses a result due to Cameron on $k$-homogeneous groups.

Recommendations

• Designing fault-tolerant systems using automorphisms
• A recursively construction scheme for super fault-tolerant Hamiltonian graphs
• Publication:4887730
• A group-invariant approach to the synthesis of fault-tolerant systems
• scientific article; zbMATH DE number 861431

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• A Graph Model for Fault-Tolerant Computing Systems
• A kind of conditional vertex connectivity of star graphs
• Automorphism group of the complete transposition graph
• Automorphism groups of Cayley graphs generated by connected transposition sets
• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• Automorphism groups of the Pancake graphs
• Data center interconnection networks are not hyperbolic
• Designing fault-tolerant systems using automorphisms
• Edge-transitivity of Cayley graphs generated by transpositions
• Transitivity of permutation groups on unordered sets

Cited in

(1)

• Designing fault-tolerant systems using automorphisms

This page was built for publication: Fault tolerant supergraphs with automorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1720338)