Search

An edge-colored graph G is called rainbow if every edge of G receives a different color. The anti-Ramsey number of t edge-disjoint rainbow spanning trees, denoted by r(n,t), is defined as the maximum number of colors in an edge-coloring of Kn containing no t edge-disjoint rainbow spanning trees. Jahanbekam and West [J. Graph Theory, 2014] conjectured that for any fixed t, r(n,t)=(n-22)+t whenever n≥2t+2≥6. In this paper, we prove this conjecture. We also determine r(n,t) when n=2t+1. Together with previous results, this gives the anti-Ramsey number of t edge-disjoint rainbow spanning trees for all values of n and t. [ABSTRACT FROM AUTHOR]

Abstract: The spectral radius of a graph G is the largest eigenvalue of its adjacency matrix. Woo and Neumaier discovered that a connected graph G with is either a dagger, an open quipu, or a closed quipu. The reverse statement is not true. Many open quipus and closed quipus have spectral radii greater than . In this paper we proved the following results. For any open quipu G on n vertices () with spectral radius less than , its diameter satisfies . This bound is tight. For any closed quipu G on n vertices () with spectral radius less than , its diameter satisfies . The upper bound is tight while the lower bound is asymptotically tight. Let be a graph with minimal spectral radius among all connected graphs on n vertices with diameter D. For and , we proved that is the unique graph obtained by attaching two paths of lengths and to a pair of antipodal vertices of the even cycle . This result is tight. Thus we settled a conjecture of Cioabaˇ–van Dam–Koolen–Lee, who previously proved a special case for and n large enough. [Copyright &y& Elsevier]

Abstract: Let be a triangle-free graph with maximum degree at most 3. Staton proved that the independence number of is at least . Heckman and Thomas conjectured that Staton’s result can be strengthened into a bound on the fractional chromatic number of , namely . Recently, Hatami and Zhu proved that . In this paper, we prove . [Copyright &y& Elsevier]

Abstract: The Randić index of a graph is defined as the sum of over all edges of , where and are the degrees of vertices and , respectively. Let be the diameter of when is connected. Aouchiche et al. (2007)  conjectured that among all connected graphs on vertices the path achieves the minimum values for both and . We prove this conjecture completely. In fact, we prove a stronger theorem: If is a connected graph, then , with equality if and only if is a path with at least three vertices. [Copyright &y& Elsevier]

Many graphs arising in various information networks exhibit the "power law" behavior –the number of vertices of degree k is proportional to k[sup -β] for some positive β.We show that if β > 2.5, the largest eigenvalue of a random power law graph is almost surely$ (1+ o(1))\sqrt{m} $$*FORMULAINSPRINGER$ where m is the maximum degree. Moreover, the klargest eigenvalues of a random power law graph with exponent β have power law distribution with exponent2β if the maximum degree is sufficiently large, where k is a function depending on β, mand d, the average degree. When 2 < β < 2.5, the largest eigenvalue is heavily concentrated at cm[sup 3-β] for some constant c depending on β and the average degree. This resultfollows from a more general theorem which shows that the largest eigenvalue of a random graph with a given expected degree sequence is determined by m, the maximum degree, and$ \tilde{d} $$*FORMULAINSPRINGER$,the weighted average of the squares of the expected degrees. We show that the k-th largest eigenvalue is almost surely [ABSTRACT FROM AUTHOR]