### Nathanson Heights and the CSS Conjecture for Cayley Graphs

#### Abstract

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

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\gamma(G)/2. Nathanson and Sullivan verified this conjecture for the directed Cayley

graph Cay(Z/NZ, EA) whose vertex set is the additive group Z/NZ and whose edge set EA is determined by

EA = {(x, x +a) : x \in Z/NZ, a \in A} when N is prime and |A| \leq (N -1)/4 by introducing “height”. In this work,

we extend the definition of height and apply to answer the CSS conjecture for Cay(Z/NZ, EA) to any positive

integer N and |A|\leq (N-1)/4.

(V, E / 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

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\gamma(G)/2. Nathanson and Sullivan verified this conjecture for the directed Cayley

graph Cay(Z/NZ, EA) whose vertex set is the additive group Z/NZ and whose edge set EA is determined by

EA = {(x, x +a) : x \in Z/NZ, a \in A} when N is prime and |A| \leq (N -1)/4 by introducing “height”. In this work,

we extend the definition of height and apply to answer the CSS conjecture for Cay(Z/NZ, EA) to any positive

integer N and |A|\leq (N-1)/4.

#### Full Text:

PDFDOI: http://dx.doi.org/10.5539/jmr.v1n1p3

This work is licensed under a Creative Commons Attribution 4.0 International License.

Journal of Mathematics Research ISSN 1916-9795 (Print) ISSN 1916-9809 (Online)

Copyright © Canadian Center of Science and Education

To make sure that you can receive messages from us, please add the 'ccsenet.org' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.

----------------------------------------------------------------------------------------------------------------------------------------------------------------------