On the b-chromatic number of Kneser graphs

In this note, we prove that for any integer n≥3 the b-chromatic number of the Kneser graph KG(m,n) is greater than or equal to . This gives an affirmative answer to a conjecture of [6].     

Bounds for the b-chromatic number of some families of graphs

In this paper we obtain some upper bounds for the b-chromatic number of K_1,s-free graphs, graphs with given minimum clique partition and bipartite graphs. These bounds are given in terms of either the clique number or the chromatic number of a graph or the biclique number for a bipartite graph. We show that all the bounds are tight.     

Ordering n-vertex cacti with matching number q by their spectral radii

Abstract

A connected graph G is a cactus if any two of its cycles have at most one common vertex. Denote by the set of n-vertex cacti with matching number q. Huang, Deng and Simi? [23] identified the unique graph with the maximum spectral radius among 2q-vertex cacti with perfect matchings. In this paper, as a continuance of it, the largest and second largest spectral radii together with the corresponding graphs among are determined. Consequently, the first two largest spectral radii together with cacti having perfect matchings are also determined.     

On the signless Laplacian index of cacti with a given number of pendant vertices

A connected graph G is a cactus if any two of its cycles have at most one common vertex. In this article, we determine graphs with the largest signless Laplacian index among all the cacti with n vertices and k pendant vertices. As a consequence, we determine the graph with the largest signless Laplacian index among all the cacti with n vertices; we also characterize the n-vertex cacti with a perfect matching having the largest signless Laplacian index.     

On the least eigenvalue of cacti

Among the cacti with n vertices and k cycles we determine a unique cactus whose least eigenvalue is minimal. We also explore cacti with n vertices and among them, we find a unique cactus whose least eigenvalue is minimal.     

On the distance spectral radius of cacti

A cactus is a connected graph in which any two cycles have at most one common vertex. In this article, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and k cycles. Also, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and r pendent vertices. Moreover, we determine the class of cacti in which the maximal distance spectral radius among all cacti with n vertices and k cycles is attained.     

More on the Harary index of cacti

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. A cactus is a connected graph in which two cycles have at most one vertex in common. In this paper, we first determine graphs with the largest Harary index among all the cacti with n vertices and a perfect matching. Then we characterize the cacti with given order, cut edges and maximum Harary index. Finally, we establish upper bounds for Harary index among all cacti with n vertices and k pendant vertices.     

Minmax subtree cover problem on cacti

Let G=(V,E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minmax subtree cover problem (MSC) asks to find a pair (X,T) of a partition X={X₁,X₂,…,X_p} of V and a set T of p subtrees T₁,T₂,…,T_p, each T_i containing X_i so as to minimize the maximum cost of the subtrees, where the cost of T_i is defined to be the sum of the weights of edges in T_i and the weights of vertices in X_i. In this paper, we propose an O(p²n) time (4-4/(p+1))-approximation algorithm for the MSC when G is a cactus.