Complete solution to a conjecture on the Randić index of triangle-free graphs

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=K_k,n−k. In this short note we give a confirmative proof for the conjecture.     

Transformation graph

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 {2K₁+K₂,K₁+K₃}{K_1,n-1,K_1,n-1+e,K_1,n-2+K₁}.     

Edge intersection graphs of systems of paths on a grid with a bounded number of bends

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 Θ(n²) is needed. We also show several results related to the classes B_k-EPG, where B_k-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 K_m,n does not belong to B_2m−3-EPG (it is known that this graph belongs to B_2m−2-EPG); for any odd integer k we have B_k-EPG B_k+1-EPG; there is no number k such that all graphs belong to B_k-EPG; only 2^O(knlog(kn)) out of all the labeled graphs with n vertices are in B_k-EPG.     

On consecutive edge magic total labeling of graphs

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.     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 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     

The connectivity of the block-intersection graphs of designs

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.     

给定边连通度的图的最小距离谱半径(英文)

本文研究了边连通度为r的n阶连通图中距离谱半径最小的极图问题,利用组合的方法,确定了K(n-1,r)为唯一的极图,其中K(n-1,r)是由完全图K_(n-1)添加一个顶点v以及连接v与K_(n-1)中r个顶点的边所构成.上述结论推广了极图理论中的相关结果.     

Super-connectivity and super-edge-connectivity for some interconnection networks

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.     

Extra edge connectivity and isoperimetric edge connectivity

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):U⊂V(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 K_3,3 and K₄, 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?6e_k(G)/k is γ_k-optimal, where e_k(G) is the maximum number of edges in a subgraph of G with order k.     

Minimum degree conditions for -linked graphs

For a fixed multigraph H with vertices w₁,…,w_m, a graph G is H-linked if for every choice of vertices v₁,…,v_m in G, there exists a subdivision of H in G such that v_i is the branch vertex representing w_i (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.     

Extremal graphs in connectivity augmentation

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     

Greedily Finding a Dense Subgraph

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)² − O(n ^− 1/3) ≤ R ≤ (1/2 + n/2k)² + 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/k²) 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.     

Euler Tours of Maximum Girth in K2 n +1 and K2 n ,2 n

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 g^E(G)= maxg(T) where the maximum is taken over all Euler tours of G.We prove that g^E(K_2n,2n)=4n–4 and 2n–3g^E(K_2n+1)2n–1 for any n2. We also show that g^E(K₇)=4. We use these results to prove the following:1)The graph K_2n,2n can be decomposed into edge disjoint paths of length k if and only if k4n–1 and the number of edges in K_2n,2n is divisible by k.2)The graph K_2n+1 can be decomposed into edge disjoint paths of length k if and only if k2n and the number edges in K_2n+1 is divisible by k.     

Hamilton cycles in random lifts of graphs

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 h₁,h₂ such that if h≥h₁ then a random n-lift of the complete graph K_h is hamiltonian and if h≥h₂ then a random n-lift of the complete bipartite graph K_h,h is hamiltonian .     

Linked graphs with restricted lengths

A graph G is k-linked if G has at least 2k vertices, and for every sequence x₁,x₂,…,x_k,y₁,y₂,…,y_k of distinct vertices, G contains k vertex-disjoint paths P₁,P₂,…,P_k such that P_i joins x_i and y_i for i=1,2,…,k. Moreover, the above defined k-linked graph G is modulo (m₁,m₂,…,m_k)-linked if, in addition, for any k-tuple (d₁,d₂,…,d_k) of natural numbers, the paths P₁,P₂,…,P_k can be chosen such that P_i has length d_i modulo m_i for i=1,2,…,k. Thomassen showed that, for each k-tuple (m₁,m₂,…,m_k) of odd positive integers, there exists a natural number f(m₁,m₂,…,m_k) such that every f(m₁,m₂,…,m_k)-connected graph is modulo (m₁,m₂,…,m_k)-linked. For m₁=m₂=…=m_k=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 G−X is a bipartite graph, where (2,2,…,2) is a k-tuple.We showed that f(m₁,m₂,…,m_k)max{14(m₁+m₂++m_k)−4k,6(m₁+m₂++m_k)−4k+36} for every k-tuple of odd positive integers. We then extend the result to allow some m_i be even integers. Let (m₁,m₂,…,m_k) be a k-tuple of natural numbers and ℓk such that m_i is odd for each i with ℓ+1ik. If G is 45(m₁+m₂++m_k)-connected, then either G has a vertex set X of order at most 2k+2ℓ−3+δ(m₁,…,m_ℓ) such that G−X is bipartite or G is modulo (2m₁,…,2m_ℓ,m_ℓ+1,…,m_k)-linked, where

Our results generalize several known results on parity-linked graphs.     

Computing Vertex Connectivity: New Bounds from Old Techniques

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{κ³ + 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 O(κ₁nmlog(n²/m)) where κ₁ ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n²/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.     

On connectivity,conductance and bootstrap percolation for a random k‐out,age‐biased graph

A uniform attachment graph (with parameter k), denoted G_n,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 G_n,k to show that the conductance of G_n,k is of order . We also study the bootstrap percolation on G_n,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.     

On the chromatic number of the general Kneser-graph

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 > n₀(k) the chromatic number of this graph is (k - 1)() + rs, where n = (k - 1)s + r, 0 ≤ r < k - 1.     

The energy of unitary cayley graphs

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 X_n has vertex set Z_n={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 X_n 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.