We introduce a new graph parameter, the rupture degree. The rupture degree for a complete graph Kn is defined as 1−n, and the rupture degree for an incomplete connected graph G is defined by r(G)=max{ω(G−X)−|X|−m(G−X):X⊂V(G), ω(G−X)>1}, where ω(G−X) is the number of components of G−X and m(G−X) is the order of a largest component of G−X. It is shown that this parameter can be used to measure the vulnerability of networks. Rupture degrees of several specific classes of graphs are determined. Formulas for the rupture degree of join graphs and some bounds of the rupture degree are given. We also obtain some Nordhaus–Gaddum type results for the rupture degree.
There is a growing interest in the identification of proteins on the proteome wide scale. Among different kinds of protein structure identification methods, graph-theoretic methods are very sharp ones. Due to their lower costs, higher effectiveness and many other advantages, they have drawn more and more researchers’ attention nowadays. Specifically, graph-theoretic methods have been widely used in homology identification, side-chain cluster identification, peptide sequencing and so on. This paper reviews several methods in solving protein structure identification problems using graph theory. We mainly introduce classical methods and mathematical models including homology modeling based on clique finding, identification of side-chain clusters in protein structures upon graph spectrum, and de novo peptide sequencing via tandem mass spectrometry using the spectrum graph model. In addition, concluding remarks and future priorities of each method are given.
It is conjectured that every edge‐colored complete graph <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> on <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> vertices satisfying <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> contains <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> vertex‐disjoint properly edge‐colored cycles. We confirm this conjecture for <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> , prove several additional weaker results for general <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> , and we establish structural properties of possible minimum counterexamples to the conjecture. We also reveal a close relationship between properly edge‐colored cycles in edge‐colored complete graphs and directed cycles in multipartite tournaments. Using this relationship and our results on edge‐colored complete graphs, we obtain several partial solutions to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen.