Search

Let G be a connected graph of order n ≥ 3 . The remoteness ρ = ρ ( G ) is the maximum, over all vertices, of the average distance from a vertex to all others. The radius r = r ( G ) is the minimum, over all vertices, of the eccentricity of a vertex. Aouchiche and Hansen (2011) conjectured that ρ − r ≥ 3 − n 4 if n is odd and ρ − r ≥ 2 n − n 2 4 ( n − 1 ) if n is even. In this paper, we confirm this conjecture. In addition, we completely characterize extremal graphs attaining the lower bound. [ABSTRACT FROM AUTHOR]

Abstract: For , and , let be the minimum value satisfying that for any connected graph of order with radius ; if no such graph exists, we set . For and , let . In this paper, we investigate the behavior of the function and determine some exact values of when or is small. [Copyright &y& Elsevier]

Abstract: Let G be a simple connected graph of order n with degree sequence in non-increasing order. The signless Laplacian spectral radius of G is the largest eigenvalue of its signless Laplacian matrix . In this paper, we give a sharp upper bound on the signless Laplacian spectral radius in terms of , which improves and generalizes some known results. [Copyright &y& Elsevier]

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: A graph is said to have a small spectral radius if it does not exceed the corresponding Hoffmann limit value. In the case of (signless) Laplacian matrix, the Hoffmann limit value is equal to , with ϵ being the real root of . Here the spectral characterization of connected graphs with small (signless) Laplacian spectral radius is considered. It is shown that all connected graphs with small Laplacian spectral radius are determined by their Laplacian spectra, and all but one of connected graphs with small signless Laplacian spectral radius are determined by their signless Laplacian spectra. [Copyright &y& Elsevier]

Abstract: The Laplacian spectral radius of a graph G is the largest eigenvalue of its Laplacian matrix. In this paper, the first three smallest values of the Laplacian spectral radii among all connected graphs with clique number are obtained. [Copyright &y& Elsevier]

Abstract: A connected graph is called a quasi-k-cyclic graph, if there exists a vertex such that is a k-cyclic graph (connected with cyclomatic number k). In this paper we identify in the set of quasi-k-cyclic graphs (for ) those graphs whose spectral radius of the adjacency matrix (and the signless Laplacian if ) is the largest. In addition, for quasi-unicyclic graphs we identify as well those graphs whose spectral radius of the adjacency matrix is the second largest. [Copyright &y& Elsevier]

Abstract: We prove sharp bounds concerning domination number, radius, order and minimum degree of a graph. In particular, we prove that if is a connected graph of order , domination number and radius , then . Equality is achieved in the upper bound if, and only if, is a path or a cycle on vertices with . Further, if has minimum degree and , then using a result due to Erdös, Pach, Pollack, and Tuza [P. Erdös, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree. J. Combin. Theory B 47 (1989), 73–79] we show that . [Copyright &y& Elsevier]

Abstract: The Randić index of a graph is defined as , where is the degree of vertex and the summation goes over all pairs of adjacent vertices , . A conjecture on for connected graph is as follows: , where denotes the radius of . We proved that the conjecture is true for biregular graphs, connected graphs with order and tricyclic graphs. [Copyright &y& Elsevier]

Abstract: The -radius is an important parameter associated with a message transmission network . In [H. Li, J.P. Li, -radius in connected graphs I, Discrete Appl. Math. (resubmitted). Also see the Ph.D. thesis 5779, Université de Paris Sud, France] we obtained upper bounds on for all given integers and . The purpose of this paper is to present improved upper bounds on for . To be specific, for any -connected graph , we show that if and if . [Copyright &y& Elsevier]