首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
The Randić index R(G) of a graph G is defined by , where d(u) is the degree of a vertex u in G and the summation extends over all edges uv of G. A conjecture about the Randić index says that for any triangle-free graph G of order n with minimum degree δk≥1, one has , where the equality holds if and only if G=Kk,nk. In this short note we give a confirmative proof for the conjecture.  相似文献   

2.
Lan Xu  Baoyindureng Wu   《Discrete Mathematics》2008,308(22):5144-5148
The transformation graph G-+- of a graph G is the graph with vertex set V(G)E(G), in which two vertices u and v are joined by an edge if one of the following conditions holds: (i) u,vV(G) and they are not adjacent in G, (ii) u,vE(G) and they are adjacent in G, (iii) one of u and v is in V(G) while the other is in E(G), and they are not incident in G. In this paper, for any graph G, we determine the connectivity and the independence number of G-+-. Furthermore, for a graph G of order n4, we show that G-+- is hamiltonian if and only if G is not isomorphic to any graph in {2K1+K2,K1+K3}{K1,n-1,K1,n-1+e,K1,n-2+K1}.  相似文献   

3.
We answer some of the questions raised by Golumbic, Lipshteyn and Stern and obtain some other results about edge intersection graphs of paths on a grid (EPG graphs). We show that for any d≥4, in order to represent every n vertex graph with maximum degree d as an edge intersection graph of n paths on a grid, a grid of area Θ(n2) is needed. We also show several results related to the classes Bk-EPG, where Bk-EPG denotes the class of graphs that have an EPG representation such that each path has at most k bends. In particular, we prove: For a fixed k and a sufficiently large n, the complete bipartite graph Km,n does not belong to B2m−3-EPG (it is known that this graph belongs to B2m−2-EPG); for any odd integer k we have Bk-EPG Bk+1-EPG; there is no number k such that all graphs belong to Bk-EPG; only 2O(knlog(kn)) out of all the labeled graphs with n vertices are in Bk-EPG.  相似文献   

4.
Let G=(V,E) be a finite (non-empty) graph, where V and E are the sets of vertices and edges of G. An edge magic total labeling is a bijection α from VE to the integers 1,2,…,n+e, with the property that for every xyE, α(x)+α(y)+α(xy)=k, for some constant k. Such a labeling is called an a-vertex consecutive edge magic total labeling if α(V)={a+1,…,a+n} and a b-edge consecutive edge magic total if α(E)={b+1,b+2,…,b+e}. In this paper we study the properties of a-vertex consecutive edge magic and b-edge consecutive edge magic graphs.  相似文献   

5.
A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and GX is not (n − |X| + 1)‐connected for any XV(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K2k + 2 − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001  相似文献   

6.
It is shown that the vertex connectivity of the block-intersection graph of a balanced incomplete block design,BIBD (v, k, 1), is equal to its minimum degree. A similar statement is proved for the edge connectivity of the block-intersection graph of a pairwise balanced design,PBD (v, K, 1). A partial result on the vertex connectivity of these graphs is also given. Minimal vertex and edge cuts for the corresponding graphs are characterized.Research supported in part by a B.C. Science Council G.R.E.A.T. Scholarship.Research supported in part by an NSERC Postdoctoral Fellowship.  相似文献   

7.
李小新  范益政  汪毅 《数学杂志》2014,34(4):671-678
本文研究了边连通度为r的n阶连通图中距离谱半径最小的极图问题,利用组合的方法,确定了K(n-1,r)为唯一的极图,其中K(n-1,r)是由完全图K_(n-1)添加一个顶点v以及连接v与K_(n-1)中r个顶点的边所构成.上述结论推广了极图理论中的相关结果.  相似文献   

8.
Let G=(V,E) be a k-regular graph with connectivity κ and edge connectivity λ. G is maximum connected if κ=k, and G is maximum edge connected if λ=k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x|(v,x)E} for some vertex vV; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)|(v,x)E} for some vertex vV. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, möbius cubes, split-stars, and recursive circulant graphs.  相似文献   

9.
Zhao Zhang 《Discrete Mathematics》2008,308(20):4560-4569
An edge set S of a connected graph G is a k-extra edge cut, if G-S is no longer connected, and each component of G-S has at least k vertices. The cardinality of a minimum k-extra edge cut, denoted by λk(G), is the k-extra edge connectivity of G. The kth isoperimetric edge connectivity γk(G) is defined as , where ω(U) is the number of edges with one end in U and the other end in . Write βk(G)=min{ω(U):UV(G),|U|=k}. A graph G with is said to be γk-optimal.In this paper, we first prove that λk(G)=γk(G) if G is a regular graph with girth g?k/2. Then, we show that except for K3,3 and K4, a 3-regular vertex/edge transitive graph is γk-optimal if and only if its girth is at least k+2. Finally, we prove that a connected d-regular edge-transitive graph with d?6ek(G)/k is γk-optimal, where ek(G) is the maximum number of edges in a subgraph of G with order k.  相似文献   

10.
For a fixed multigraph H with vertices w1,…,wm, a graph G is H-linked if for every choice of vertices v1,…,vm in G, there exists a subdivision of H in G such that vi is the branch vertex representing wi (for all i). This generalizes the notions of k-linked, k-connected, and k-ordered graphs.Given a connected multigraph H with k edges and minimum degree at least two and n7.5k, we determine the least integer d such that every n-vertex simple graph with minimum degree at least d is H-linked. This value D(H,n) appears to equal the least integer d such that every n-vertex graph with minimum degree at least d is b(H)-connected, where b(H) is the maximum number of edges in a bipartite subgraph of H.  相似文献   

11.
Let A(n, k, t) denote the smallest integer e for which every k‐connected graph on n vertices can be made (k + t)‐connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge‐connectivity and also for directed vertex‐connectivity. For undirected vertex‐connectivity we determine A(n, k, 1) for all values of n and k. We also describe the graphs that attain the extremal values. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 179–193, 1999  相似文献   

12.
Greedily Finding a Dense Subgraph   总被引:3,自引:0,他引:3  
Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)2 − O(n − 1/3) ≤ R ≤ (1/2 + n/2k)2 + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k − 1) − O(1/k) ≤ R ≤ 2(n/k − 1) + O(n/k2) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.  相似文献   

13.
Given an eulerian graph G and an Euler tour T of G, the girth of T, denoted by g(T), is the minimum integer k such that some segment of k+1 consecutive vertices of T is a cycle of length k in G. Let gE(G)= maxg(T) where the maximum is taken over all Euler tours of G.We prove that gE(K2n,2n)=4n–4 and 2n–3gE(K2n+1)2n–1 for any n2. We also show that gE(K7)=4. We use these results to prove the following:1)The graph K2n,2n can be decomposed into edge disjoint paths of length k if and only if k4n–1 and the number of edges in K2n,2n is divisible by k.2)The graph K2n+1 can be decomposed into edge disjoint paths of length k if and only if k2n and the number edges in K2n+1 is divisible by k.  相似文献   

14.
An n-lift of a graph K is a graph with vertex set V(K)×[n], and for each edge (i,j)E(K) there is a perfect matching between {i}×[n] and {j}×[n]. If these matchings are chosen independently and uniformly at random then we say that we have a random n-lift. We show that there are constants h1,h2 such that if hh1 then a random n-lift of the complete graph Kh is hamiltonian and if hh2 then a random n-lift of the complete bipartite graph Kh,h is hamiltonian .  相似文献   

15.
Computing Vertex Connectivity: New Bounds from Old Techniques   总被引:1,自引:0,他引:1  
The vertex connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{κ3 + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O1nmlog(n2/m)) where κ1m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424–446) that computes edge connectivity.  相似文献   

16.
A graph G is k-linked if G has at least 2k vertices, and for every sequence x1,x2,…,xk,y1,y2,…,yk of distinct vertices, G contains k vertex-disjoint paths P1,P2,…,Pk such that Pi joins xi and yi for i=1,2,…,k. Moreover, the above defined k-linked graph G is modulo (m1,m2,…,mk)-linked if, in addition, for any k-tuple (d1,d2,…,dk) of natural numbers, the paths P1,P2,…,Pk can be chosen such that Pi has length di modulo mi for i=1,2,…,k. Thomassen showed that, for each k-tuple (m1,m2,…,mk) of odd positive integers, there exists a natural number f(m1,m2,…,mk) such that every f(m1,m2,…,mk)-connected graph is modulo (m1,m2,…,mk)-linked. For m1=m2=…=mk=2, he showed in another article that there exists a natural number g(2,k) such that every g(2,k)-connected graph G is modulo (2,2,…,2)-linked or there is XV(G) such that |X|4k−3 and GX is a bipartite graph, where (2,2,…,2) is a k-tuple.We showed that f(m1,m2,…,mk)max{14(m1+m2++mk)−4k,6(m1+m2++mk)−4k+36} for every k-tuple of odd positive integers. We then extend the result to allow some mi be even integers. Let (m1,m2,…,mk) be a k-tuple of natural numbers and k such that mi is odd for each i with +1ik. If G is 45(m1+m2++mk)-connected, then either G has a vertex set X of order at most 2k+2−3+δ(m1,…,m) such that GX is bipartite or G is modulo (2m1,…,2m,m+1,…,mk)-linked, where
Our results generalize several known results on parity-linked graphs.  相似文献   

17.
A uniform attachment graph (with parameter k), denoted Gn,k in the paper, is a random graph on the vertex set [n], where each vertex v makes k selections from [v ? 1] uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well‐studied random graphs: k‐out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of Gn,k to show that the conductance of Gn,k is of order . We also study the bootstrap percolation on Gn,k, where r infected neighbors infect a vertex, and show that if the probability of initial infection of a vertex is negligible compared to then with high probability (whp) the disease will not spread to the whole vertex set, and if this probability exceeds by a sub‐logarithmical factor then the disease whp will spread to the whole vertex set.  相似文献   

18.
Given integers k, n, 2 < k < n, let us define a graph with vertex set V = {F ?{1, 2, …, n}: ∩F = k}, and (F, F') is an edge if |F ∩ F′| ≤ 1. We show that for n > n0(k) the chromatic number of this graph is (k - 1)() + rs, where n = (k - 1)s + r, 0 ≤ r < k - 1.  相似文献   

19.
The energy of unitary cayley graphs   总被引:1,自引:0,他引:1  
A graph G of order n is called hyperenergetic if E(G)>2n-2, where E(G) denotes the energy of G. The unitary Cayley graph Xn has vertex set Zn={0,1,2,…,n-1} and vertices a and b are adjacent, if gcd(a-b,n)=1. These graphs have integral spectrum and play an important role in modeling quantum spin networks supporting the perfect state transfer. We show that the unitary Cayley graph Xn is hyperenergetic if and only if n has at least two prime factors greater than 2 or at least three distinct prime factors. In addition, we calculate the energy of the complement of unitary Cayley graph and prove that is hyperenergetic if and only if n has at least two distinct prime factors and n≠2p, where p is a prime number. By extending this approach, for every fixed , we construct families of k hyperenergetic non-cospectral integral circulant n-vertex graphs with equal energy.  相似文献   

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

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