On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

Four new sums of graphs and their Wiener indices

The Wiener index is the sum of distances between all vertex pairs in a connected graph. This notion was motivated by various mathematical properties and chemical applications. In this paper we introduce four new operations on graphs and study the Wiener indices of the resulting graphs.     

Minimizing the least eigenvalue of unicyclic graphs with fixed diameter

Let U(n,d) be the set of unicyclic graphs on n vertices with diameter d. In this article, we determine the unique graph with minimal least eigenvalue among all graphs in U(n,d). It is found that the extremal graph is different from that for the corresponding problem on maximal eigenvalue as done by Liu et al. [H.Q. Liu, M. Lu, F. Tian, On the spectral radius of unicyclic graphs with fixed diameter, Linear Algebra Appl. 420 (2007) 449-457].     

Semiharmonic trees and monocyclic graphs

A graph G is defined to be semiharmonic if there is a constant μ (necessarily a natural number) such that, for every vertex v, the number of walks of length 3 starting in v equals μd_G(v) where d_G(v) is the degree of v. We determine all finite semiharmonic trees and monocyclic graphs.     

On the roots of Wiener polynomials of graphs

The Wiener polynomial of a connected graph $G$ is defined as $W(G;x)=\sum x^{d(u,v)}$, where $d(u,v)$ denotes the distance between $u$ and $v$, and the sum is taken over all unordered pairs of distinct vertices of $G$. We examine the nature and location of the roots of Wiener polynomials of graphs, and in particular trees. We show that while the maximum modulus among all roots of Wiener polynomials of graphs of order $n$ is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)?1$, the maximum modulus among all roots of Wiener polynomials of trees of order $n$ grows linearly in $n$. We prove that the closure of the collection of real roots of Wiener polynomials of all graphs is precisely $(?\infty ,0]$, while in the case of trees, it contains $(?\infty ,?1]$. Finally, we demonstrate that the imaginary parts and (positive) real parts of roots of Wiener polynomials can be arbitrarily large.     

The number of independent sets in unicyclic graphs with a given diameter

Let U_n,d denote the set of unicyclic graphs with a given diameter d. In this paper, the unique unicyclic graph in U_n,d with the maximum number of independent sets, is characterized.     

Unicyclic and bicyclic graphs having minimum degree distance

In this paper characterizations of connected unicyclic and bicyclic graphs in terms of the degree sequence, as well as the graphs in these classes minimal with respect to the degree distance are given.     

The maximum number of maximal independent sets in unicyclic connected graphs

In this paper, we determine the maximum number of maximal independent sets in a unicyclic connected graph. We also find a class of graphs achieving this maximum value.     

On the Reverse Wiener Indices of Unicyclic Graphs

We determine the maximum values of the reverse Wiener indices of the unicyclic graphs with given cycle length, number of pendent vertices and maximum degree, respectively, and characterize the extremal graphs. We also determine the unicyclic graphs of given cycle length and diameter with minimum Wiener index.      

Domination subdivision numbers of trees

A set S of vertices of a graph G=(V,E) is a dominating set if every vertex of V(G)?S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number  is the minimum number of edges that must be subdivided in order to increase the domination number. Velammal showed that for any tree T of order at least 3, . In this paper, we give two characterizations of trees whose domination subdivision number is 3 and a linear algorithm for recognizing them.     

On the spectral radii of unicyclic graphs with fixed matching number

In this paper, the first five sharp upper bounds on the spectral radii of unicyclic graphs with fixed matching number are presented. The first ten spectral radii over the class of unicyclic graphs on a given number of vertices and the first four spectral radii of unicyclic graphs with perfect matchings are also given, respectively.     

Total outer-connected domination numbers of trees

Let G=(V,E) be a graph without an isolated vertex. A set DV(G) is a total dominating set if D is dominating, and the induced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total dominating set of G. A set DV(G) is a total outer-connected dominating set if D is total dominating, and the induced subgraph G[V(G)−D] is a connected graph. The total outer-connected domination number of G is the minimum cardinality of a total outer-connected dominating set of G. We characterize trees with equal total domination and total outer-connected domination numbers. We give a lower bound for the total outer-connected domination number of trees and we characterize the extremal trees.     

Average distances and distance domination numbers

Let k be a positive integer and G be a simple connected graph with order n. The average distance μ(G) of G is defined to be the average value of distances over all pairs of vertices of G. A subset D of vertices in G is said to be a k-dominating set of G if every vertex of V(G)−D is within distance k from some vertex of D. The minimum cardinality among all k-dominating sets of G is called the k-domination number γ_k(G) of G. In this paper tight upper bounds are established for μ(G), as functions of n, k and γ_k(G), which generalizes the earlier results of Dankelmann [P. Dankelmann, Average distance and domination number, Discrete Appl. Math. 80 (1997) 21-35] for k=1.     

On crossing numbers of geometric proximity graphs

Let P be a set of n points in the plane. A geometric proximity graph on P is a graph where two points are connected by a straight-line segment if they satisfy some prescribed proximity rule. We consider four classes of higher order proximity graphs, namely, the k-nearest neighbor graph, the k-relative neighborhood graph, the k-Gabriel graph and the k-Delaunay graph. For k=0 (k=1 in the case of the k-nearest neighbor graph) these graphs are plane, but for higher values of k in general they contain crossings. In this paper, we provide lower and upper bounds on their minimum and maximum number of crossings. We give general bounds and we also study particular cases that are especially interesting from the viewpoint of applications. These cases include the 1-Delaunay graph and the k-nearest neighbor graph for small values of k.