共查询到20条相似文献,搜索用时 15 毫秒
1.
图G的Wiener指数是指图G中所有顶点对间的距离之和,即W(G)=∑dc(u,u),{u,u}CG其中de(u,u)表示G中顶点u,u之间的距离.三圈图是指边数与顶点数之差等于2的连通图,任意两个圈至多只有一个公共点的三圈图记为T_n~3.研究了三圈图T_n~3的Wiener指数,给出了其具有最小、次小Wiener指数的图结构. 相似文献
2.
3.
The Hamiltonian index of a graph G is defined as
h(G)=min{m:Lm(G) is Hamiltonian}. 相似文献
4.
Let G be a graph. Then the hamiltonian index h(G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l≥3. We also show that for any two 2-connected nonhamiltonian graphs G and with at least 74 vertices. The upper bounds are all sharp. 相似文献
5.
Let G be a graph. For u,vV(G) with distG(u,v)=2, denote JG(u,v)={wNG(u)∩NG(v)|NG(w)NG(u)NG(v){u,v}}. A graph G is called quasi claw-free if JG(u,v)≠ for any u,vV(G) with distG(u,v)=2. In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. In this paper we show that every 4-connected line graph of a quasi claw-free graph is hamiltonian connected. 相似文献
6.
The strong chromatic index of a class of graphs 总被引:1,自引:0,他引:1
Jianzhuan Wu 《Discrete Mathematics》2008,308(24):6254-6261
The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ′(G)≤6. Let H0 be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H0 and d(x)+d(y)≤5 for any edge xy of G then sχ′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs. 相似文献
7.
Iwao Sato 《Discrete Mathematics》2007,307(2):237-245
We treat zeta functions and complexities of semiregular bipartite graphs. Furthermore, we give formulas for zeta function and the complexity of a line graph of a semiregular bipartite graph. As a corollary, we present the complexity of a line graph of a complete bipartite graph. 相似文献
8.
Orest Bucicovschi 《Discrete Applied Mathematics》2008,156(18):3518-3521
In this note, we study the degree distance of a graph which is a degree analogue of the Wiener index. Given n and e, we determine the minimum degree distance of a connected graph of order n and size e. 相似文献
9.
10.
Let be a connected graph with vertex set and edge set . For a subset of , the Steiner distance of is the minimum size of a connected subgraph whose vertex set contains . For an integer with , the Steiner-Wiener index is . In this paper, we introduce some transformations for trees that do not increase their Steiner -Wiener index for . Using these transformations, we get a sharp lower bound on Steiner -Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well. 相似文献
11.
Let G be a simple connected graph, and let d i be the degree of its i-th vertex. The sum-connectivity index of the graph G is defined as χ ( G ) = Σ v i v j ∈ E ( G ) ? ( d i + d j ) − 1 / 2 . We discuss the effect on χ(G) of inserting an edge into a graph. Moreover, we obtain the relations between sum-connectivity index and Randić index. 相似文献
12.
13.
In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of and does there exist an -cycle decomposition of In this paper, the above question is answered for In fact, it is shown that the -fold line graph of the complete graph has a -decomposition if and only if and 相似文献
14.
In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time. 相似文献
15.
Various topological indices have been put forward in different studies, from biochemistry to pure mathematics. Among them, the Wiener index, the number of subtrees, and the Randi? index have received great attention from mathematicians. In the study of extremal problems regarding these indices among trees, one interesting phenomenon is that they share the same extremal tree structures. Much effort was devoted to the study of the correlations between these various indices. In this note we provide a common characteristic (the ‘semi-regular’ property) of these extremal structures, with respect to the above mentioned indices, among trees with a given maximum degree. This observation leads to a more unified approach for characterizing these extremal structures. As an application/example, we illustrate the idea by studying the extremal trees, regarding the sum of distances between all pairs of leaves of a tree, a new index, which recently appeared in phylogenetic tree reconstruction, and the study of the neighborhood of trees. 相似文献
16.
S. Morteza Mirafzal 《Discrete Mathematics》2018,341(1):217-220
The Kneser graph has as vertices all -element subsets of and an edge between any two vertices that are disjoint. If , then is called an odd graph. Let and . In the present paper, we show that if the Kneser graph is of even order where is an odd integer or both of the integers are even, then is a vertex-transitive non Cayley graph. Although, these are special cases of Godsil [7], unlike his proof that uses some very deep group-theoretical facts, ours uses no heavy group-theoretic facts. We obtain our results by using some rather elementary facts of number theory and group theory. We show that ‘almost all’ odd graphs are of even order, and consequently are vertex-transitive non Cayley graphs. Finally, we show that if is an even integer such that is not of the form for some , then the line graph of the odd graph is a vertex-transitive non Cayley graph. 相似文献
17.
Russell Merris 《Linear and Multilinear Algebra》2013,61(2-3):275-285
If G is a graph on n vertices, its Laplacian matrix L(G) = D(G) - A(G) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. The main purpose of this note is to continue the study of the positive definite, doubly stochastic graph matrix (In + L(G))?1= ω(G) = (wij). If, for example, w(G) = min wij, then w(G)≥0 with equality if and only if G is disconnected and w(G) ≤ l/(n + 1) with equality if and only if G = Kn. If i¦j, then wii ≥2wij, with equality if and only if the ith vertex has degree n - 1. In a sense made precise in the note, max w,, identifies most remote vertices of G. Relations between these new graph invariants and the algebraic connectivity emerge naturally from the fact that the second largest eigenvalue of ω(G) is 1/(1 + a(G)). 相似文献
18.
19.
Russell Merris 《Linear and Multilinear Algebra》1998,45(2):275-285
If G is a graph on n vertices, its Laplacian matrix L(G) = D(G) - A(G) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. The main purpose of this note is to continue the study of the positive definite, doubly stochastic graph matrix (In + L(G))-1= ω(G) = (wij). If, for example, w(G) = min wij, then w(G)≥0 with equality if and only if G is disconnected and w(G) ≤ l/(n + 1) with equality if and only if G = Kn. If i¦j, then wii ≥2wij, with equality if and only if the ith vertex has degree n - 1. In a sense made precise in the note, max w,, identifies most remote vertices of G. Relations between these new graph invariants and the algebraic connectivity emerge naturally from the fact that the second largest eigenvalue of ω(G) is 1/(1 + a(G)). 相似文献