The bisection width is the minimum number of edges required to split the vertex set of a graph into two (nearly) equal parts. Monien and Preis proved that the bisection width of a cubic graph with n nodes is bounded above by n∕6+o(n). Here we show that every cubic graph of even order n≥16 has bisection width less than n∕2, thus these graphs violate the even cut condition (ECC). All edge-minimal subcubic graphs satisfying ECC are also described. The bisection width is a reference parameter to compare networks for parallel architectures; ECC is a property necessary for bottleneck free all-to-all communications.

We prove that every 18-tough chordal graph has a Hamiltonian cycle. © 1998 John Wiley & Sons, Inc. Networks 31: 29–38, 1998

An induced path-cycle double cover (IPCDC) of a simple graph G is a family ℱ = {F1, …, Fk} of induced paths and cycles of G such that if Fi ∩ Fj ≠ ⊘, then Fi ∩ Fj is a vertex or an edge, for i ≠ j, each edge of G appears in precisely two of the Fi's, and each vertex of G appears in precisely three of the Fi's. In this paper, we prove that recognizing triangle-free simple graphs with an IPCDC is NP-complete by reducing the 3-Satisfiability problem to finding an IPCDC. The dependency graph of a 3-uniform hypergraph H = (V, E) is the graph with vertex set E in which two hyperedges are joined if and only if they share exactly two elements. We show that a triangle-free simple graph is the dependency graph of a 3-uniform hypergraph if and only if it has an IPCDC. Consequently, the problem of recognizing dependency graphs of 3-uniform hypergraphs is NP-complete. © 1998 John Wiley & Sons, Inc. Networks 31: 1–10, 1998