On the second largest eigenvalue of line graphs

In this paper all connected line graphs whose second largest eigenvalue does not exceed 1 are characterized. Besides, all minimal line graphs with second largest eigenvalue greater than 1 are determined. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 61–66, 1998     

Lambda composition

A lambda in a graph G is two edges uv and vw such that uw is not an edge. A subgraph A of G is called a lambda-subgraph if every lambda of G has both or neither of its edges in A. We describe the decomposition of a graph into its lambda subgraphs and use this to prove a decomposition theorem of Gallai (Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66). A corollary is that a graph is perfect if and only if each of its edge-minimal lambda subgraphs is. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:9–16, 1997     

Degree sequence conditions for maximally edge-connected graphs and digraphs

In this paper we give simple degree sequence conditions for the equality of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue conditions for bipartite (di-)graphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:27–34, 1997     

A counterexample to the bold conjecture

A pair of vertices (x,y) of a graph G is an o-critical pair if o(G + xy) > o(G), where G + xy denotes the graph obtained by adding the edge xy to G and o(H) is the clique number of H. The o-critical pairs are never edges in G. A maximal stable set S of G is called a forced color class of G if S meets every o-clique of G, and o-critical pairs within S form a connected graph. In 1993, G. Bacsó raised the following conjecture which implies the famous Strong Perfect Graph Conjecture: If G is a uniquely o-colorable perfect graph, then G has at least one forced color class. This conjecture is called the Bold Conjecture. Here we show a simple counterexample to it. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 165–168, 1997     

Degree sums for edges and cycle lengths in graphs

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference—the length of a longest cycle—of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length between 3 and the circumference, unless G is complete bipartite. If G is 1-tough then it is pancyclic or G = K_r,r with r = n/2. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 253–256, 1997     

Network Dynamics in Elemental Assimilation and Metabolism

Metabolism and physiology frequently follow non-linear rhythmic patterns which are reflected in concepts of homeostasis and circadian rhythms, yet few biomarkers are studied as dynamical systems. For instance, healthy human development depends on the assimilation and metabolism of essential elements, often accompanied by exposures to non-essential elements which may be toxic. In this study, we applied laser ablation-inductively coupled plasma-mass spectrometry (LA-ICP-MS) to reconstruct longitudinal exposure profiles of essential and non-essential elements throughout prenatal and early post-natal development. We applied cross-recurrence quantification analysis (CRQA) to characterize dynamics involved in elemental integration, and to construct a graph-theory based analysis of elemental metabolism. Our findings show how exposure to lead, a well-characterized toxicant, perturbs the metabolism of essential elements. In particular, our findings indicate that high levels of lead exposure dysregulate global aspects of metabolic network connectivity. For example, the magnitude of each element’s degree was increased in children exposed to high lead levels. Similarly, high lead exposure yielded discrete effects on specific essential elements, particularly zinc and magnesium, which showed reduced network metrics compared to other elements. In sum, this approach presents a new, systems-based perspective on the dynamics involved in elemental metabolism during critical periods of human development.     

Chromatic‐index‐critical graphs of even order

A k‐critical (multi‐) graph G has maximum degree k, chromatic index χ′(G) = k + 1, and χ′(G − e) < k + 1 for each edge e of G. For each k ≥ 3, we construct k‐critical (multi‐) graphs with certain properties to obtain counterexamples to some well‐known conjectures. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 27–36, 1999     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999