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

     

Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:

the generalized Bethe tree B,

a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,

a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,

a graph obtained from the cycle C_r by attaching B, by its root, to each vertex of the cycle, and

a tree obtained from the path P_r by attaching B, by its root, to each vertex of the path,

is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.

     

Vertex and edge PI indices of Cartesian product graphs

The Padmakar-Ivan (PI) index of a graph G is the sum over all edges uv of G of the number of edges which are not equidistant from u and v. In this paper, the notion of vertex PI index of a graph is introduced. We apply this notion to compute an exact expression for the PI index of Cartesian product of graphs. This extends a result by Klavzar [On the PI index: PI-partitions and Cartesian product graphs, MATCH Commun. Math. Comput. Chem. 57 (2007) 573-586] for bipartite graphs. Some important properties of vertex PI index are also investigated.     

Lower bounds for the game colouring number of partial k-trees and planar graphs

This paper discusses the game colouring number of partial k-trees and planar graphs. Let col_g(PT_k) and col_g(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this paper, we prove that col_g(PT_k)=3k+2 and col_g(P)?11. We also prove that the game colouring number col_g(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then col_g(H)?col_g(G).     

The eccentric connectivity index of nanotubes and nanotori

Let G be a molecular graph. The eccentric connectivity index ξ^c(G) is defined as ξ^c(G)=∑_u∈V(G)deg_G(u)ε_G(u), where deg_G(u) denotes the degree of vertex u and ε_G(u) is the largest distance between u and any other vertex v of G. In this paper exact formulas for the eccentric connectivity index of TUC₄C₈(S) nanotube and TC₄C₈(S) nanotorus are given.     

The Laplacian spectral radius of some bipartite graphs

In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K_1,k and one vertex of degree n of K_m,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs.     

On upper bounds for Laplacian graph eigenvalues

In this paper, we obtain the following upper bound for the largest Laplacian graph eigenvalue λ(G):

     

Heterochromatic tree partition numbers for complete bipartite graphs

An r-edge-coloring of a graph G is a surjective assignment of r colors to the edges of G. A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t_r(G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we give an explicit formula for the heterochromatic tree partition number of an r-edge-colored complete bipartite graph K_m,n.     

The choice number of random bipartite graphs

A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log₂(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship.     

Nearly bipartite graphs with large chromatic number

P. Erdős and A. Hajnal asked the following question. Does there exist a constant ε>0 with the following property: If every subgraphH of a graphG can be made bipartite by the omission of at most ε|H| edges where |H| denotes the number of vertices ofH thenx(H) ≦ 3. The aim of this note is to give a negative answer to this question and consider the analogous problem for hypergraphs. The first was done also by L. Lovász who used a different construction.     

New upper bounds on the spectral radius of trees with the given number of vertices and maximum degree

This paper studies the problem of estimating the spectral radius of trees with the given number of vertices and maximum degree. We obtain the new upper bounds on the spectral radius of the trees, and the results are the best upper bounds expressed by the number of vertices and maximum degree, at present.     

Spectral bounds for the betweenness of a graph

In this paper we find spectral bounds (Laplacian matrix) for the vertex and the edge betweenness of a graph. We also relate the edge betweenness with the isoperimetric number and the edge forwarding and edge expansion indices of the graph allowing a new upper bound on its diameter. The results are of interest as they can be used in the study of communication properties of real networks, in particular for dynamical processes taking place on them (broadcasting, network synchronization, virus spreading, etc.).     

On the Estrada and Laplacian Estrada indices of graphs

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of G. The Laplacian Estrada index of a graph G is defined as , where μ₁,μ₂,…,μ_n are the Laplacian eigenvalues of G. An edge grafting operation on a graph moves a pendent edge between two pendent paths. We study the change of Estrada index of graph under edge grafting operation between two pendent paths at two adjacent vertices. As the application, we give the result on the change of Laplacian Estrada index of bipartite graph under edge grafting operation between two pendent paths at the same vertex. We also determine the unique tree with minimum Laplacian Estrada index among the set of trees with given maximum degree, and the unique trees with maximum Laplacian Estrada indices among the set of trees with given diameter, number of pendent vertices, matching number, independence number and domination number, respectively.     

Functional centrality in graphs

In this article, we introduce the functional centrality as a generalization of the subgraph centrality. We propose a general method for characterizing nodes in the graph according to the number of closed walks starting and ending at the node. Closed walks are appropriately weighted according to the topological features that we need to measure.     

Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

The Estrada index of trees

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of its adjacency matrix. We determine the unique tree with maximum Estrada index among the set of trees with given number of pendant vertices. As applications, we determine trees with maximum Estrada index among the set of trees with given matching number, independence number, and domination number, respectively. Finally, we give a proof of a conjecture in [J. Li, X. Li, L. Wang, The minimal Estrada index of trees with two maximum degree vertices, MATCH Commun. Math. Comput. Chem. 64 (2010) 799-810] on trees with minimum Estrada index among the set of trees with two adjacent vertices of maximum degree.     

Covering of graphs by complete bipartite subgraphs; Complexity of 0–1 matrices

We prove that the edge set of an arbitrary simple graphG onn vertices can be covered by at mostn−[log₂ n]+1 complete bipartite subgraphs ofG. If the weight of a subgraph is the number of its vertices, then there always exists a cover with total weightc(n ²/logn) and this bound is sharp apart from a constant factor. Our result answers a problem of T. G. Tarján. Dedicated to Paul Erdős on his seventieth birthday     

Colorings and orientations of graphs

Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: IfG is a directed graph with maximum outdegreed, and if the number of Eulerian subgraphs ofG with an even number of edges differs from the number of Eulerian subgraphs with an odd number of edges then for any assignment of a setS(v) ofd+1 colors for each vertexv ofG there is a legal vertex-coloring ofG assigning to each vertexv a color fromS(v).Research supported in part by a United States-Israel BSF Grant and by a Bergmann Memorial Grant.     

On bounds for the index of double nested graphs

The index of a simple graph is the largest eigenvalue of its adjacency matrix. It is well-known that in the set of all connected graphs with fixed order and size the graphs with maximal index are nested split graphs. It was recently observed that double nested graphs assume the same role if we restrict ourselves to bipartite graphs. In this paper we provide some bounds (lower and upper) for the index of double nested graphs. Some computational results are also included.     

Estimating the Estrada index

Let G be a graph on n vertices, and let λ₁,λ₂,…,λ_n be its eigenvalues. The Estrada index of G is a recently introduced graph invariant, defined as . We establish lower and upper bounds for EE in terms of the number of vertices and number of edges. Also some inequalities between EE and the energy of G are obtained.