Nathanson Heights and the CSS Conjecture for Cayley Graphs
Abstract
(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: https://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.
----------------------------------------------------------------------------------------------------------------------------------------------------------------------