Nathanson Heights and the CSS Conjecture for Cayley Graphs

DOI10.5539/JMR.V1N1P3MaRDI QIDQ5324642zbMATH OpenOpenAlexWikidataFDO

Authors Yotsanan Meemark, Chaiwat Pinthubthaworn

Publication date 3 August 2009

Published in Journal of Mathematics Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/0805.0341

zbMATH Keywords

Cayley graphsCSS conjectureNathanson heights

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Abstract: Let $G$ be a finite directed graph, $$ the minimum size of a subset $X$ of edges such that the graph $G^{\prime }=(V,EsmallsetminusX)$ 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 $$. They conjectured a sharper bound (so called the "CSS conjecture") that $$. Nathanson and Sullivan verified this conjecture for the directed Cayley graph $$ whose vertex set is the additive group $$ and whose edge set $E_A$ is determined by $$ 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 $$ to any positive integer $N$.

Recommendations

• On the Chudnovsky-Seymour-Sullivan conjecture on cycles in triangle-free digraphs
• Counterexamples to ``A conjecture on induced subgraphs of Cayley graphs
• Cycles in dense digraphs
• scientific article
• On directed triangles in digraphs

Cited in

(1)

• scientific article; zbMATH DE number 1820188 (Why is no real title available?)

This page was built for publication: Nathanson Heights and the CSS Conjecture for Cayley Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5324642)