Search

It is well known that if G is a multigraph then χ′( G)≥ χ′( G):=max {Δ( G),Γ( G)}, where χ′( G) is the chromatic index of G, χ′( G) is the fractional chromatic index of G, Δ( G) is the maximum degree of G, and Γ( G)=max {2| E( G[ U])|/(| U|−1): U⊆ V( G),| U|≥3, | U| is odd}. The conjecture that χ′( G)≤max {Δ( G)+1,⌈Γ( G)⌉} was made independently by Goldberg (Discret. Anal. 23:3-7, ), Anderson (Math. Scand. 40:161-175, ), and Seymour (Proc. Lond. Math. Soc. 38:423-460, ). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′( G)≤ χ′( G)+ c χ′( G) when χ′( G)> D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′( G)> ⌊(11Δ( G)+8)/10 ⌋; and Scheide recently improved this bound to χ′( G)> ⌊(15Δ( G)+12)/14 ⌋. We prove this conjecture for multigraphs G with $\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor$ , improving the above mentioned results. As a consequence, for multigraphs G with $\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}$ the answer to a 1964 problem of Vizing is in the affirmative. [ABSTRACT FROM AUTHOR]

To better understand the biological significance of Ca2+, we report a comprehensive statistical analysis of calcium-binding proteins from the Protein Data Bank to identify structural parameters associated with EF-hand and non-EF-hand Ca2+-binding sites. Comparatively, non-EF-hand sites utilize lower coordination numbers (6 ± 2 vs. 7 ± 1), fewer protein ligands (4 ± 2 vs. 6 ± 1), and more water ligands (2 ± 2 vs. 1 ± 0) than EF-hand sites. The orders of ligand preference for non-EF-hand and EF-hand sites, respectively, were H2O (33.1%) > side-chain Asp (24.5%) > main-chain carbonyl (23.9%) > side-chain Glu (10.4%), and side-chain Asp (29.7%) > side-chain Glu (26.6%) > main-chain carbonyl (21.4%) > H2O (13.3%). Less formal negative charge was observed in the non-EF-hand than in the EF-hand binding sites (1 ± 1 vs. 3 ± 1). Additionally, over 20% of non-EF-hand sites had formal charge values of zero due to increased utilization of water and carbonyl oxygen ligands. Moreover, the EF-hand sites presented a narrower range of ligand distances and bond angles than non-EF-hand sites, possibly owing to the highly conserved helix–loop–helix motif. Significant differences between ligand types (carbonyl, side chain, bidentate) demonstrated that angles associated with each type must be classified separately, and the EF-hand side-chain Ca–O–C angles exhibited an unusual bimodal quality consistent with an Asp distribution that differed from the Gaussian model observed for non-EF-hand proteins. The results of this survey more accurately describe differences between EF-hand and non-EF-hand proteins and provide new parameters for the prediction and design of different classes of Ca2+-binding proteins. [ABSTRACT FROM AUTHOR]

Let G be a graph and u, v be two distinct vertices of G. A u?v path P is called nonseparating if G?V( P) is connected. The purpose of this paper is to study the number of nonseparating u?v path for two arbitrary vertices u and v of a given graph. For a positive integer k, we will show that there is a minimum integer a( k) so that if G is an a( k)-connected graph and u and v are two arbitrary vertices in G, then there exist k vertex disjoint paths P 1[ u, v], P 2[ u, v], . . ., P k[ u, v], such that G?V ( P i[ u, v]) is connected for every i ( i = 1, 2, ..., k). In fact, we will prove that a( k) = 22 k+2. It is known that a(1) = 3.. A result of Tutte showed that a(2) = 3. We show that a(3) = 6. In addition, we prove that if G is a 5-connected graph, then for every pair of vertices u and v there exists a path P[ u, v] such that G?V( P[ u, v]) is 2-connected. [ABSTRACT FROM AUTHOR]