首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 125 毫秒
1.
Let D(G)=(di,j)n×n denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vi and vj in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, we give some graft transformations that decrease and increase ?(G) and prove that the graph (obtained from the star Sn on n (n is not equal to 4, 5) vertices by adding an edge connecting two pendent vertices) has minimal distance spectral radius among unicyclic graphs on n vertices; while (obtained from a triangle K3 by attaching pendent path Pn−3 to one of its vertices) has maximal distance spectral radius among unicyclic graphs on n vertices.  相似文献   

2.
Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=vV(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=uV(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.  相似文献   

3.
For two vertices u and v in a strong digraph D, the strong distance sd(u,v) between u and v is the minimum size (the number of arcs) of a strong sub-digraph of D containing u and v. For a vertex v of D, the strong eccentricity se(v) is the strong distance between v and a vertex farthest from v. The strong radius srad(D) (resp. strong diameter sdiam(D)) is the minimum (resp. maximum) strong eccentricity among the vertices of D. The lower (resp. upper) orientable strong radius srad(G) (resp. SRAD(G)) of a graph G is the minimum (resp. maximum) strong radius over all strong orientations of G. The lower (resp. upper) orientable strong diameter sdiam(G) (resp. SDIAM(G)) of a graph G is the minimum (resp. maximum) strong diameter over all strong orientations of G. In this paper, we determine the lower orientable strong radius and diameter of complete k-partite graphs, and give the upper orientable strong diameter and the bounds on the upper orientable strong radius of complete k-partite graphs. We also find an error about the lower orientable strong diameter of complete bipartite graph Km,n given in [Y.-L. Lai, F.-H. Chiang, C.-H. Lin, T.-C. Yu, Strong distance of complete bipartite graphs, The 19th Workshop on Combinatorial Mathematics and Computation Theory, 2002, pp. 12-16], and give a rigorous proof of a revised conclusion about sdiam(Km,n).  相似文献   

4.
The eccentric distance sum is a novel topological index that offers a vast potential for structure activity/property relationships. For a graph G, it is defined as ξd(G)=vVε(v)D(v), where ε(v) is the eccentricity of the vertex v and D(v)=uV(G)d(u,v) is the sum of all distances from the vertex v. Motivated by [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 934-944], in this paper we characterize the extremal trees and graphs with maximal eccentric distance sum. Various lower and upper bounds for the eccentric distance sum in terms of other graph invariants including the Wiener index, the degree distance, eccentric connectivity index, independence number, connectivity, matching number, chromatic number and clique number are established. In addition, we present explicit formulae for the values of eccentric distance sum for the Cartesian product, applied to some graphs of chemical interest (like nanotubes and nanotori).  相似文献   

5.
6.
The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph G=(V,E) and two nonadjacent vertices vi and vj in V(G) of G, recall that G+vivj is the supergraph formed from G by adding an edge between vertices vi and vj. Denote the Harary index of G and G+vivj by H(G) and H(G+vivj), respectively. We obtain lower and upper bounds on H(G+vivj)−H(G), and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained.  相似文献   

7.
A shortest path connecting two vertices u and v is called a u-v geodesic. The distance between u and v in a graph G, denoted by dG(u,v), is the number of edges in a u-v geodesic. A graph G with n vertices is panconnected if, for each pair of vertices u,vV(G) and for each integer k with dG(u,v)?k?n-1, there is a path of length k in G that connects u and v. A graph G with n vertices is geodesic-pancyclic if, for each pair of vertices u,vV(G), every u-v geodesic lies on every cycle of length k satisfying max{2dG(u,v),3}?k?n. In this paper, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs can be applied to geodesic-pancyclic graphs.  相似文献   

8.
Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex vi by d(vi). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v1),d(v2),…,d(vn)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q1(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q1(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q1(G). Then we present three sharp lower bounds for q1(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.  相似文献   

9.
A graph G is a k-sphere graph if there are k-dimensional real vectors v 1,…,v n such that ijE(G) if and only if the distance between v i and v j is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v 1,…,v n such that ijE(G) if and only if the dot product of v i and v j is at least 1.  相似文献   

10.
Let G be a connected graph with vertex set V(G) = {v1, v2,..., v n }. The distance matrix D(G) = (d ij )n×n is the matrix indexed by the vertices of G, where d ij denotes the distance between the vertices v i and v j . Suppose that λ1(D) ≥ λ2(D) ≥... ≥ λ n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号