Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T21:34:28.515Z Has data issue: false hasContentIssue false

Ramanujan Signing of Regular Graphs

Published online by Cambridge University Press:  03 November 2004

YONATAN BILU
Affiliation:
Institute of Computer Science, Hebrew University of Jerusalem, Jerusalem 91904, Israel (e-mail: johnblue@cs.huji.ac.il, nati@cs.huji.ac.il)
NATHAN LINIAL
Affiliation:
Institute of Computer Science, Hebrew University of Jerusalem, Jerusalem 91904, Israel (e-mail: johnblue@cs.huji.ac.il, nati@cs.huji.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A signing of a graph $G=(V,E)$ is a function $s:E \rightarrow \{-1,1\}$. A signing defines a graph $\widehat{G}$, called a {\em 2-lift of $G$}, with vertex set $V(G)\times\{-1,1\}$. The vertices $(u,x)$ and $(v,y)$ are adjacent iff $(u,v) \in E(G)$, and $x \cdot y = s(u,v)$. The corresponding signed adjacency matrix$A_{G,s}$ is a symmetric $\{-1,0,1\}$-matrix, with $(A_{G,s})_{u,v} = s(u,v)$ if $(u,v) \in E$, and $0$ otherwise.

Information

Type
Problem Section
Copyright
2004 Cambridge University Press