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.

A hypergraph is $k$-irregular if there is no set of $k$ vertices all of which have the same degree. We asymptotically determine the probability that a random uniform hypergraph is $k$-irregular.

We prove that in a random $3$-uniform or $4$-uniform hypergraph of order $n$ the probability that some two vertices have the same degree tends to one as $n\to\infty$.

An adjacent vertex distinguishing edge‐coloring of a simple graph G is a proper edge‐coloring of G such that no pair of adjacent vertices meets the same set of colors. The minimum number of colors $\chi^\prime_a(G)$ required to give G an adjacent vertex distinguishing coloring is studied for graphs with no isolated edge. We prove $\chi^\prime_a(G)\le5$ for such graphs with maximum degree $\Delta(G)=3$ and prove $\chi^\prime_a(G)\le\Delta(G)+2$ for bipartite graphs. These bounds are tight. For k‐chromatic graphs G without isolated edges we prove a weaker result of the form $\chi^\prime_a(G)=\Delta(G)+O(\log k)$.

The bar visibility number of a graph G, denoted b(G), is the minimum t such that G can be represented by assigning each vertex x the set S x of points in at most t horizontal segments in the plane so that uv $\in$ E(G) if and only if some point of S u sees some point of S v via a vertical segment of positive width unobstructed by assigned points. Among our results are the following: (1) Every planar graph has bar visibility number at most 2, which is sharp. (2) $r\le b(K_{m,n})\le r+1$, where $r=\big\lceil\frac{mn+4}{2m+2n}\big\rceil$. (3) $b(K_n)=\lceil{n/6}\rceil$. (4) If G has n vertices, then $b(G)\le \lceil{n/6}\rceil+2$.

This is the first half of a two-part paper devoted to on-line 3-colorable graphs. Here on-line 3-colorable triangle-free graphs are characterized by a finite list of forbidden induced subgraphs. The key role in our approach is played by the family of graphs which are both triangle- and (2K2 + K1)-free. Characterization of this family is given by introducing a bipartite modular decomposition concept. This decomposition, combined with the greedy algorithm, culminates in an on-line 3-coloring algorithm for this family. On the other hand, based on the characterization of this family, all 22 forbidden subgraphs of on-line 3-colorable triangle-free graphs are determined. As a corollary, we obtain the 10 forbidden subgraphs of on-line 3-colorable bipartite graphs. The forbidden subgraphs in the finite basis characterization are on-line 4-critical, i.e., they are on-line 4-chromatic but their proper induced subgraphs are on-line 3-colorable. The results of this paper are applied in the companion paper [Discrete Math., 177 (1997), pp. 99--122] to obtain the finite basis characterization of connected on-line 3-colorable graphs (with 51 4-critical subgraphs). However, perhaps surprisingly, connectivity (or the triangle-free property) is essential in a finite basis characterization: there are infinitely many on-line 4-critical graphs.

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

Abstract Let G be a multigraph of maximum degree Δ and with a set of t vertices of degree one, called terminals. We call G a (Δ, t)‐network if for any pairing of its terminals there exist edge‐disjoint paths in G between those pairs (t is even). The concept of (Δ, t)‐networks is introduced to model the situation when switching processors having Δ ports are to be connected in such a way that simultaneous communication is possible for any pairing of the free ports. We establish some properties of (Δ, t)‐networks. In particular, we investigate optimal (or near‐optimal) networks and obtain lower and upper bounds on the function n(Δ, t), the minimum number of interior nodes a (Δ, t)‐network can have.