Given a graph G = ( V , E ) on n vertices and an integer k between 1 and n − 1 , the k -token graph F k ( G ) has vertices representing the k -subsets of V , and two vertices are adjacent if their symmetric difference is the two end-vertices of an edge in E . Using the theory of Markov chains of random walks and the interchange process, it was proved that the algebraic connectivities (second smallest Laplacian eigenvalues) of G and F k ( G ) coincide, but a combinatorial/algebraic proof has been shown elusive. In this paper, we use the latter approach and prove that such equality holds for different new classes of graphs under perturbations, such as extended cycles, extended complete bipartite graphs, kite graphs, and graphs with a cut clique. Kite graphs are formed by a graph (head) with several paths (tail) rooted at the same vertex and with exciting properties. For instance, we show that the different eigenvalues of a kite graph are also eigenvalues of its perturbed graph obtained by adding edges. Moreover, as a particular case of one of our theorems, we generalize a recent result of Barik and Verma (2024) about graphs with a cut vertex of degree n − 1 . Along the way, we give conditions under which the perturbed graph G + u v , with u v ∈ E , has the same algebraic connectivity as G .

In the study of edge colorings of graphs, critical graphs are of particular importance. One classical result concerning the structure of critical graphs is known as Vizing’s Adjacency Lemma. This lemma provides useful structural information about the neighborhood of a vertex in a critical graph. Zhang introduced an adjacency lemma dealing with the second neighborhood of a vertex in a critical graph. Both of these adjacency lemmas are useful tools for proving classification results on edge colorings. In this paper, we present an adjacency lemma on critical signed graphs with even maximum degree. This new adjacency lemma can be interpreted as a local extension of Zhang’s Adjacency Lemma. As an application of the new lemma, we show that a signed planar graph with maximum degree Δ ≥ 6 in which every 6-cycle has at most one chord is Δ -edge-colorable.

We consider the computational complexity of spanning tree problems involving the graphical function-index. This index was recently introduced by Li and Peng as a unification of a long list of chemical and topological indices. We present a number of unified approaches to determine the NP-completeness and APX-completeness of maximum and minimum spanning tree problems involving this index. We give many examples of well-studied topological indices for which the associated complexity questions are covered by our results.

For an edge-colored graph, its minimum color degree is the minimum number of distinct colors appearing on the edges incident with a vertex, and its maximum monochromatic degree is the maximum number of edges with the same color incident with a vertex. A cycle in an edge-colored graph is called properly colored if any two consecutive edges of the cycle have distinct colors. We investigate sufficient conditions in terms of the minimum color degree and maximum monochromatic degree for the existence of short properly colored cycles in edge-colored complete graphs. In particular, we obtain sharp results for the existence of properly colored C4’s, and we characterize the extremal graphs for several known results on the existence of properly colored triangles. Moreover, we obtain sharp sufficient conditions guaranteeing that every vertex is contained in a properly colored triangle or C4, respectively.

Let $G$ be a graph on $n$ vertices. An induced subgraph $H$ of $G$ is called heavy if there exist two nonadjacent vertices in $H$ with degree sum at least $n$ in $G$. We say that $G$ is $H$-heavy if every induced subgraph of $G$ isomorphic to $H$ is heavy. For a family $\mathcal{H}$ of graphs, $G$ is called $\mathcal{H}$-heavy if $G$ is $H$-heavy for every $H\in\mathcal{H}$. In this paper we characterize all connected graphs $R$ and $S$ other than $P_3$ (the path on three vertices) such that every 2-connected $\{R,S\}$-heavy graph is Hamiltonian. This extends several previous results on forbidden subgraph conditions for Hamiltonian graphs.

This paper mainly focuses on the integrated importance measure (IIM) of component states based on loss of system performance. To describe the impact of each component state, we first introduce the performance function of the multi-state system. Then, we present the definition of IIM of component states. We demonstrate its corresponding physical meaning, and then analyze the relationships between IIM and Griffith importance, Wu importance, and Natvig importance. Secondly, we present the evaluation method of IIM for multi-state systems. Thirdly, the characteristics of IIM of component states are discussed. Finally, we demonstrate a numerical example, and an application to an offshore oil and gas production system for IIM to verify the proposed method. The results show that 1) the IIM of component states concerns not only the probability distributions and transition intensities of the states of the object component, but also the change in the system performance under the change of the state distribution of the object component; and 2) IIM can be used to identify the key state of a component that affects the system performance most.

Protein complexes are essential entities that per form the major cellular processes and biological functions in live organisms. The identification of component proteins in a complex from protein-protein interaction (PPI) networks is an important step to understand the organization and interaction of gene products. In existing literature, methods for identifying protein complexes typically start from a selected seed, commonly a vertex (a single protein), in a PPI network. However, in many circumstances, a single protein seed is not enough to generate a meaningful complex, or more than one protein is known in a complex. In this paper, we present an improved seed-growth style algorithm to identify protein complexes from PPI networks based on the concept of graph entropy. Different from existing methods, the seed is assumed to be a clique (e.g., a vertex, an edge, a triangle) in a PPI network. The computational experiments have been conducted on PPI network of S. cerevisiae. The results have shown that the larger cliques are considered as seeds, the better the presented method performs in terms off-score. In particular, up to K3-cliques are included as seeds, the average f-score is 57.32%, which is better than that of existing methods.

The scattering number of a noncomplete connected graph G is defined by s(G) = max{ω(G − X) − |X|: X ⊂ V(G), ω(G − X) ≥ 2}, where ω(G − X) denotes the number of components of the graph G − X. In this paper, we show that this parameter can be used to measure the vulnerability of a graph. To some extent, it represents a trade-off between the amount of work done to damage the network and how badly the network is damaged. The relationship between the scattering number and some other parameters of a graph is discussed. Furthermore, we give the Nordhaus—Gaddum-type result for scattering number. © 2001 John Wiley & Sons, Inc.