Variable neighborhood search for extremal graphs. 23. On the Randi? index and the chromatic number

Let G=(V,E) be a simple graph with vertex degrees d₁,d₂,…,d_n. The Randi? index R(G) is equal to the sum over all edges (i,j)∈E of weights . We prove several conjectures, obtained by the system AutoGraphiX, relating R(G) and the chromatic number χ(G). The main result is χ(G)≤2R(G). To prove it, we also show that if v∈V is a vertex of minimum degree δ of G, G−v the graph obtained from G by deleting v and all incident edges, and Δ the maximum degree of G, then .     

Proof of conjecture involving the second largest signless Laplacian eigenvalue and the index of graphs

Let G = (V, E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the signless Laplacian matrix of G is Q(G) = D(G) + A(G). In [5], Cvetkovi? et al. have given the following conjecture involving the second largest signless Laplacian eigenvalue (q₂) and the index (λ₁) of graph G (see also Aouchiche and Hansen [1]):

     

Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality

Let G be a connected graph, suppose that v is a vertex of G, and denote the subgraph formed from G by deleting vertex v by G?v. Denote the algebraic connectivities of G and G?v by α(G) and α(G?v), respectively. In this paper, we consider the functions ?(v)=α(G)−α(G?v) and , provide attainable upper and lower bounds on both functions, and characterise the equality cases in those bounds. The function κ yields a measure of vertex centrality, and we apply that measure to analyse certain graphs arising from food webs.     

Graphs with maximal signless Laplacian spectral radius

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. It is known that connected graphs G that maximize the signless Laplacian spectral radius ρ(Q(G)) over all connected graphs with given numbers of vertices and edges are (degree) maximal. For a maximal graph G with n vertices and r distinct vertex degrees δ_r>δ_r-1>?>δ₁, it is proved that ρ(Q(G))<ρ(Q(H)) for some maximal graph H with n+1 (respectively, n) vertices and the same number of edges as G if either G has precisely two dominating vertices or there exists an integer such that δ_i+δ_r+1-i?n+1 (respectively, δ_i+δ_r+1-i?δ_l+δ_r-l+1). Graphs that maximize ρ(Q(G)) over the class of graphs with m edges and m-k vertices, for k=0,1,2,3, are completely determined.     

Bandwidth of the corona of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(u)-f(v)|:uv∈E(G)} taken over all injective integer numberings f of G. The corona of two graphs G and H, written as G°H, is the graph obtained by taking one copy of G and |V(G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. In this paper, we investigate the bandwidth of the corona of two graphs. For a graph G, we denote the connectivity of G by κ(G). Let G be a graph on n vertices with B(G)=κ(G)=k?2 and let H be a graph of order m. Let c,p and q be three integers satisfying 1?c?k-1 and . We define h_i=(2k-1)m+(k-i)(⌊(2k-1)m/i⌋+1)+1 for i=1,2,…,k and b=max{⌈(n(m+1)-qm-1)/(p+2)⌉,⌈(n(m+1)+k-q-1)/(p+3)⌉}. Then, among other results, we prove that

     

Eigenvalues and edge-connectivity of regular graphs

In this paper, we show that if the second largest eigenvalue of a d-regular graph is less than , then the graph is k-edge-connected. When k is 2 or 3, we prove stronger results. Let ρ(d) denote the largest root of x³-(d-3)x²-(3d-2)x-2=0. We show that if the second largest eigenvalue of a d-regular graph G is less than ρ(d), then G is 2-edge-connected and we prove that if the second largest eigenvalue of G is less than , then G is 3-edge-connected.     

The largest eigenvalue of unicyclic graphs

Let G be a simple graph. Let λ₁(G) and μ₁(G) denote the largest eigenvalue of the adjacency matrix and the Laplacian matrix of G, respectively. Let Δ denote the largest vertex degree. If G has just one cycle, then

     

On the spanning fan-connectivity of graphs

Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, C_k(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k^∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ^∗(G), is the maximum integer k such that G is w^∗-connected for 1≤w≤k if G is 1^∗-connected.Let x be a vertex in G and let U={y₁,y₂,…,y_k} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, F_k(x,U), is a set of internally-disjoint paths {P₁,P₂,…,P_k} such that P_i is a path connecting x to y_i for 1≤i≤k and . A graph G is k^∗-fan-connected (or -connected) if there exists a spanning F_k(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ^∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k^∗-pipeline-connected.     

New upper bounds on the spectral radius of unicyclic graphs

Let G=(V(G),E(G)) be a unicyclic simple undirected graph with largest vertex degree Δ. Let C_r be the unique cycle of G. The graph G-E(C_r) is a forest of r rooted trees T₁,T₂,…,T_r with root vertices v₁,v₂,…,v_r, respectively. Let

     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(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 q₁(G). Then we present three sharp lower bounds for q₁(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.     

Bounds on the index of the signless Laplacian of a graph

Let G=(V,E) be a simple, undirected graph of order n and size m with vertex set V, edge set E, adjacency matrix A and vertex degrees Δ=d₁≥d₂≥?≥d_n=δ. The average degree of the neighbor of vertex v_i is . Let D be the diagonal matrix of degrees of G. Then L(G)=D(G)−A(G) is the Laplacian matrix of G and Q(G)=D(G)+A(G) the signless Laplacian matrix of G. Let μ₁(G) denote the index of L(G) and q₁(G) the index of Q(G). We survey upper bounds on μ₁(G) and q₁(G) given in terms of the d_i and m_i, as well as the numbers of common neighbors of pairs of vertices. It is well known that μ₁(G)≤q₁(G). We show that many but not all upper bounds on μ₁(G) are still valid for q₁(G).     

Some graft transformations and its application on a distance spectrum

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j 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 S_n 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 K₃ by attaching pendent path P_n−3 to one of its vertices) has maximal distance spectral radius among unicyclic graphs on n vertices.     

Domination with exponential decay

Let G be a graph and S⊆V(G). For each vertex u∈S and for each v∈V(G)−S, we define to be the length of a shortest path in 〈V(G)−(S−{u})〉 if such a path exists, and ∞ otherwise. Let v∈V(G). We define if v⁄∈S, and w_S(v)=2 if v∈S. If, for each v∈V(G), we have w_S(v)≥1, then S is an exponential dominating set. The smallest cardinality of an exponential dominating set is the exponential domination number, γ_e(G). In this paper, we prove: (i) that if G is a connected graph of diameter d, then γ_e(G)≥(d+2)/4, and, (ii) that if G is a connected graph of order n, then .     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

Spectral radius and Hamiltonicity of graphs

Let G be a graph of order n and μ(G) be the largest eigenvalue of its adjacency matrix. Let be the complement of G.Write K_n-1+v for the complete graph on n-1 vertices together with an isolated vertex, and K_n-1+e for the complete graph on n-1 vertices with a pendent edge.We show that:If μ(G)?n-2, then G contains a Hamiltonian path unless G=K_n-1+v; if strict inequality holds, then G contains a Hamiltonian cycle unless G=K_n-1+e.If , then G contains a Hamiltonian path unless G=K_n-1+v.If , then G contains a Hamiltonian cycle unless G=K_n-1+e.     

Inverse degree and edge-connectivity

Let G be a connected graph with vertex set V(G), order n=|V(G)|, minimum degree δ and edge-connectivity λ. Define the inverse degree of G as , where d(v) denotes the degree of the vertex v. We show that if

     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).