Nathanson's Heights and the CSS Conjecture for Cayley Graphs

Details Nathanson's Heights and the CSS Conjecture for Cayley Graphs Nathanson's Heights and the CSS Conjecture for Cayley Graphs

2008-05-03

arxiv.org/abs/0805.0341v1

Mathematics

Number Theory

9 pages

Scientific paper

Let $G$ be a finite directed graph, $\beta(G)$ the minimum size of a subset $X$ of edges such that the graph $G' = (V,E \smallsetminus X)$ is directed acyclic and $\gamma(G)$ the number of pairs of nonadjacent vertices in the undirected graph obtained from $G$ by replacing each directed edge with an undirected edge. Chudnovsky, Seymour and Sullivan \cite{CSS07} proved that if $G$ is triangle-free, then $\beta(G) \leq \gamma(G)$. They conjectured a sharper bound (so called the "CSS conjecture") that $\beta(G) \leq \dfrac{\gamma(G)}{2}$. Nathanson and Sullivan verified this conjecture for the directed Cayley graph $\Cay(\bbZ/N\bbZ, E_A)$ whose vertex set is the additive group $\bbZ/N\bbZ$ and whose edge set $E_A$ is determined by $E_A = {(x,x+a) : x \in \bbZ/N\bbZ, a \in A}$ when $N$ is prime in \cite{NS07} by introducing "height". In this work, we extend the definition of height and the proof of CSS conjecture for $\Cay(\bbZ/N\bbZ, E_A)$ to any positive integer $N$.

Affiliated with

Also associated with

No associations

Rating

Nathanson's Heights and the CSS Conjecture for Cayley Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nathanson's Heights and the CSS Conjecture for Cayley Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nathanson's Heights and the CSS Conjecture for Cayley Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-512597