Labeled versus unlabeled distributed Cayley networks

DOI10.1016/0166-218X(94)00070-3MaRDI QIDQ1917232zbMATH OpenFDO

Authors Evangelos Kranakis, D. Krizanc

Publication date 5 August 1996

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

Full work available at URL https://doi.org/10.1016/0166-218X(94)00070-3

zbMATH Keywords

anonymous Cayley networkBoolean functionsCayley graphlabellabeling

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Boolean functions (06E30)

Review text

The authors consider Cayley graphs with the following natural labeling: the label of the edge \((u, v)\) is \(u^{- 1} v\). An anonymous Cayley network is a Cayley graph whose nodes are anonymous. In this paper, the labeling problem on anonymous Cayley networks is studied. In general, oriented Cayley networks can compute more Boolean functions than unoriented Cayley networks. Sufficient conditions for the labeling to be strong are provided. For abelian groups with canonical sets of generators a characterization of groups with strong labelings is given.

Recommendations

• Symmetries and sense of direction in labeled graphs
• Cayley graphs
• scientific article; zbMATH DE number 1151833
• Assigning labels in unknown anonymous networks (extended abstract)

Cites work

• A group-theoretic model for symmetric interconnection networks
• Boolean Functions, Invariance Groups, and Parallel Complexity
• Computing functions on asynchronous anonymous networks
• Computing on an anonymous ring
• Graphen mit transitiver Automorphismengruppe
• scientific article; zbMATH DE number 3864485 (Why is no real title available?)
• scientific article; zbMATH DE number 4058846 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• scientific article; zbMATH DE number 3328108 (Why is no real title available?)
• Network Orientation
• On a Theorem of Sabidussi
• On recognizing a string on an anonymous ring
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Uniform self-stabilizing ring orientation
• Vertex-transitive graphs

Cited in

(3)

• Computing on anonymous networks with sense of direction
• Minimal sense of direction in regular networks
• TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION

This page was built for publication: Labeled versus unlabeled distributed Cayley networks

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