Nathanson Heights and the CSS Conjecture for Cayley Graphs

Yotsanan Meemark, Chaiwat Pinthubthaworn

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.

Full Text: PDF DOI: 10.5539/jmr.v1n1p3

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 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.