Path decompositions of triangle-free graphs

Let G be a graph with n vertices. A path decomposition of G is a set of edge-disjoint paths containing all the edges of G. Let $p(G)$ denote the minimum number of paths needed in a path decomposition of G. Gallai Conjecture asserts that if G is connected, then $p(G)\le ?n/2?$. If G is allowed to be disconnected, then the upper bound $?\frac{3}{4}n?$ for $p(G)$ was obtained by Donald [7], which was improved to $?\frac{2}{3}n?$ independently by Dean and Kouider [6] and Yan [14]. For graphs consisting of vertex-disjoint triangles, $?\frac{2}{3}n?$ is reached and so this bound is tight. If triangles are forbidden in G, then $p(G)\le ?\frac{g+1}{2g}n?$ can be derived from the result of Harding and McGuinness [11], where g denotes the girth of G. In this paper, we also focus on triangle-free graphs and prove that $p(G)\le ?3n/5?$, which improves the above result with $g=4$.     

On eigenfunctions and maximal cliques of generalised Paley graphs of square order

Let GP $(q^2,m)$ be the m-Paley graph defined on the finite field with order $q^2$. We study eigenfunctions and maximal cliques in generalised Paley graphs GP $(q^2,m)$, where $m|(q+1)$. In particular, we explicitly construct maximal cliques of size $\frac{q+1}{m}$ or $\frac{q+1}{m}+1$ in GP $(q^2,m)$, and show the weight-distribution bound on the cardinality of the support of an eigenfunction is tight for the smallest eigenvalue $-\frac{q+1}{m}$ of GP $(q^2,m)$. These new results extend the work of Baker et al. and Goryainov et al. on Paley graphs of square order. We also study the stability of the Erdős-Ko-Rado theorem for GP $(q^2,m)$ (first proved by Sziklai).