Search

Abstract: We study the Hosoya index of trees with -matchings and characterize the trees with -matchings and the fourth and fifth minimal Hosoya index respectively. [Copyright &y& Elsevier]

In this paper, using the properties of chromatic polynomial and adjoint polynomial, we characterize all graphs having chromatic polynomial ∑l⩽m0l/m0−l(λ)l. [Copyright &y& Elsevier]

• We propose some lower and upper bounds for the g -component connectivity along with their sharpness. • We characterize some trees and general graphs with the given g -component connectivity. • We suggest characterizations of graphs with given g -component connectivity and Erdös-Gallai-type problems for the g -component connectivity in this paper. Connectivity is a classic metric to evaluate reliability of multiprocessor system under the circumstances of processor failures. Based on connectivity, more refined quantitative indicators for fault tolerance of multiprocessor system have been extensively explored. The g -component connectivity of a graph G , denoted by c κ g (G) , is the minimum number of vertices whose removal from G results in a disconnected graph with at least g -components. So far, the values of the g -component (edge) connectivity of special networks with small g have been extensively investigated. For general graphs, the results of the g -component connectivity are very few. In this paper, we propose some lower and upper bounds for the g -component connectivity along with their sharpness, and then suggest some characterization of trees and general graphs with given g -component connectivity. Furthermore, we fix some related extremal problems. [ABSTRACT FROM AUTHOR]

Let G σ be an oriented graph and P s ( G σ ; x ) = det ( x I − S ( G σ ) ) be the skew-characteristic polynomial of its skew-adjacency matrix S ( G σ ) . The skew-energy of G σ is defined to be the sum of the absolute values of eigenvalues of S ( G σ ) . In this paper, we firstly find a novel relation between the coefficients of skew-characteristic polynomial of unicyclic graph with the third largest skew-energy and bicyclic oriented graphs, and then use it along with other techniques to characterize the bicyclic oriented graphs with the second largest skew-energy. [ABSTRACT FROM AUTHOR]

Connectivity and diagnosability are very important parameters for the tolerant of an interconnection network. Let F be a vertex set of graph G , the g -extra connectivity k ˜ (g) (G) of G requires each component of G − F has at least (g + 1) vertices. The g -extra conditional diagnosability t ˜ (g) (G) is the maximum number of faulty vertices that the graph can be guaranteed to identify under the condition that each fault-free component has at least g + 1 vertices. In this paper, we study the problem about the g -extra connectivity k ˜ (g) (G) of the round matching composition networks, and obtain some results about the g -extra conditional diagnosability of the round matching composition networks under the PMC model and MM* model, respectively. [ABSTRACT FROM AUTHOR]

Abstract: Let be the characteristic polynomial of a graph . Two graphs and are cospectral, denoted by , if . By we denote the cospectral equivalence class determined by under “”. A graph is said to be determined by its spectrum (or simply is a DS-graph) if whenever . In this paper, we determine the cospectral equivalence classes of three kinds of graphs having an isolated vertex, find several DS-graphs and identify the graph that has the fourth minimum index among all connected graphs with vertices. [Copyright &y& Elsevier]