Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+
 Title Keywords Abstract Author All
Search Results: 1 - 10 of 100 matches for " "
 Mathematics , 2015, Abstract: The terminal Wiener index of a tree is the sum of distances for all pairs of pendent vertices, which recently arises in the study of phylogenetic tree reconstruction and the neighborhood of trees. This paper presents a sharp upper and lower bounds for the terminal Wiener index in terms of its order and diameter and characterizes all extremal trees which attain these bounds. In addition, we investigate the properties of extremal trees which attain the maximum terminal Wiener index among all trees of order $n$ with fixed maximum degree.
 Mathematics , 2013, Abstract: Heydari \cite{heydari2013} presented very nice formulae for the Wiener and terminal Wiener indices of generalized Bethe trees. It is pity that there are some errors for the formulae. In this paper, we correct these errors and characterize all trees with the minimum terminal Wiener index among all the trees of order $n$ and with maximum degree $\Delta$.
 Mathematics , 2013, Abstract: Let $\lambda_1,\dots,\lambda_n$ be the eigenvalues of a graph $G$. For any $k\geq 0$, the $k$-th spectral moment of $G$ is defined by $\M_k(G)=\lambda_1^k+\dots+\lambda_n^k$. We use the fact that $\M_k(G)$ is also the number of closed walks of length $k$ in $G$ to show that among trees $T$ whose degree sequence is $D$ or majorized by $D$, $\M_k(T)$ is maximized by the greedy tree with degree sequence $D$ (constructed by assigning the highest degree in $D$ to the root, the second-, third-, \dots highest degrees to the neighbors of the root, and so on) for any $k\geq 0$. Several corollaries follow, in particular a conjecture of Ili\'c and Stevanovi\'c on trees with given maximum degree, which in turn implies a conjecture of Gutman, Furtula, Markovi\'c and Gli\v{s}i\'c on the Estrada index of such trees, which is defined as $\EE(G)=e^{\lambda_1}+\dots+e^{\lambda_n}$.
 Mathematics , 2012, Abstract: In this paper, we investigate the structures of an extremal tree which has the minimal number of subtrees in the set of all trees with the given degree sequence of a tree. In particular, the extremal trees must be caterpillar and but in general not unique. Moreover, all extremal trees with a given degree sequence $\pi=(d_1, ..., d_5, 1,..., 1)$ have been characterized.
 Mathematics , 2012, Abstract: Let $A(G)$ be the adjacency matrix of graph $G$ with eigenvalues $\lambda_1(G), \lambda_2(G),..., \lambda_n(G)$ in non-increasing order. The number $S_k(G):=\sum_{i=1}^{n}\lambda_i^{k}(G)\, (k=0, 1,..., n-1)$ is called the $k$th spectral moment of $G$. Let $S(G) = (S_0(G), S_1(G),..., S_{n-1}(G))$ be the sequence of spectral moments of $G.$ For two graphs $G_1, G_2$, we have $G_1\prec_{s}G_2$ if for some $k \in \{1,2,3,...,n-1\}$, we have $S_i(G_1) = S_i(G_2)\, ,\, i = 0, 1,..., k-1$ and $S_k(G_1)  Computer Science , 2011, DOI: 10.1016/j.disc.2012.01.034 Abstract: A proper vertex-colouring of a graph G is said to be locally identifying if for any pair u,v of adjacent vertices with distinct closed neighbourhoods, the sets of colours in the closed neighbourhoods of u and v are different. We show that any graph G has a locally identifying colouring with$2\Delta^2-3\Delta+3$colours, where$\Delta\$ is the maximum degree of G, answering in a positive way a question asked by Esperet et al. We also provide similar results for locally identifying colourings which have the property that the colours in the neighbourhood of each vertex are all different and apply our method to the class of chordal graphs.