A $t$-bar visibility representation of a graph assigns each vertex up to $t$ horizontal bars in the plane so that two vertices are adjacent if and only if some bar for one vertex can see some bar for the other via an unobstructed vertical channel of positive width. The least $t$ such that $G$ has a $t$-bar visibility representation is the bar visibility number of $G$, denoted by $b(G)$. For the complete bipartite graph $K_{m,n}$, the lower bound $b(K_{m,n})\ge\lceil{\frac{mn+4}{2m+2n}}\rceil$ from Euler's formula is well known. We prove that equality holds.

The Reconstruction Conjecture of Ulam asserts that, for n ≥ 3, every n-vertex graph is determined by the multiset of its induced subgraphs with n-1 vertices. The conjecture is known to hold for various special classes of graphs but remains wide open. We survey results on the more general conjecture by Kelly from 1957 that for every positive integerlthere exists Ml(with M1=3) such that when n ≥ Mlevery n-vertex graph is determined by the multiset of its induced subgraphs with n-lvertices.

A k-bar visibility representation of a digraph $G$ assigns each vertex at most $k$ horizontal segments in the plane so that $G$ has an arc $uv$ if and only if some segment for $u$ “sees” some segment for $v$ above it by a vertical line of sight. The (bar) visibility number $b(G)$ of a digraph $G$ is the least $k$ permitting such a representation. Among other results, we show that $b(G) \leq 4$ when $G$ is a planar digraph (reducing to 3 when the underlying graph has no triangles), $b(G) \leq 2$ when $G$ is outerplanar, and $b(G) \leq (n+10)/3$ when $G$ has $n$ vertices. When $G$ is the $n$-vertex transitive tournament, $b(G) \leq 7n/24 + 2\sqrt{n \log n}$, improving to $b(G) < 3n/14 + 42$ when $n$ is sufficiently large. Our tools include arboricity, interval number, and Steiner systems.

In the domination game on a graph $G$, two players called Dominator and Staller alternately select vertices of $G$. Each vertex chosen must strictly increase the number of vertices dominated; the game ends when the chosen set becomes a dominating set of $G$. Dominator aims to minimize the size of the resulting dominating set, while Staller aims to maximize it. When both players play optimally, the size of the dominating set produced is the game domination number of $G$, denoted by $\gamma_g(G)$ when Dominator plays first and by $\gamma_g^\prime(G)$ when Staller plays first. We prove that $\gamma_g(G) \le 7n/11$ when $G$ is an isolate-free $n$-vertex forest and that $\gamma_g(G) \le \left\lceil7n/10\right\rceil$ for any isolate-free $n$-vertex graph. In both cases we conjecture that $\gamma_g(G) \le 3n/5$ and prove it when $G$ is a forest of nontrivial caterpillars. We also resolve conjectures of Brešar, Klavžar, and Rall by showing that always $\gamma_g^\prime(G)\le\gamma_g(G)+1$, that for $k\ge2$ there are graphs $G$ satisfying $\gamma_g(G) = 2k$ and $\gamma_g^\prime(G) = 2k-1$, and that $\gamma_g^\prime(G) \ge \gamma_g(G)$ when $G$ is a forest. Our results follow from fundamental lemmas about the domination game that simplify its analysis and may be useful in future research.

Let $G$ be a weighted graph in which each vertex initially has weight $1$. A total acquisition move transfers all the weight from a vertex $u$ to a neighboring vertex $v$, under the condition that before the move the weight on $v$ is at least as large as the weight on $u$. The (total) acquisition number of $G$, written $a_{t}(G)$, is the minimum size of the set of vertices with positive weight after a sequence of total acquisition moves. Among connected $n$-vertex graphs, $a_{t}(G)$ is maximized by trees. The maximum is $\Theta(\sqrt{n\lg n})$ for trees with diameter $4$ or $5$. It is $\left\lfloor{(n+1)/3}\right\rfloor$ for trees with diameter between $6$ and $\frac23(n+1)$, and it is $\left\lceil{(2n-1-D)/4}\right\rceil$ for trees with diameter $D$ when $\frac{2}{3}(n+1)\le D\le n-1$. We characterize trees with acquisition number 1, which permits testing $a_{t}(G)\le k$ in time $O(n^{k+2})$ on trees. If $G\ne C_5$, then $\min\{a_{t}(G),a_{t}(\overline{G})\}=1$. If $G$ has diameter $2$, then $a_{t}(G)\le 32\ln n\ln\ln n$; we conjecture a constant upper bound. Indeed, $a_{t}(G)=1$ when $G$ has diameter $2$ and no $4$-cycle, except for four graphs with acquisition number $2$. Deleting one edge of an $n$-vertex graph cannot increase $a_{t}$ by more than $6.84\sqrt n$, but we construct an $n$-vertex tree with an edge whose deletion increases it by more than $\frac12\sqrt{n}$. We also obtain multiplicative upper bounds under products.

A Roman dominating function of a graph G is a labeling $f\colon\,V(G)\to\{0,1,2\}$ such that every vertex with label 0 has a neighbor with label 2. The Roman domination number $\gamma_R(G)$ of G is the minimum of $\sum_{v\in V(G)}f(v)$ over such functions. Let G be a connected n-vertex graph. We prove that $\gamma_R(G)\leq4n/5$, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for $\gamma_R(G)+\gamma_R(\overline{G})$ and $\gamma_R(G)\gamma_R(\overline{G})$, improving known results for domination number. We prove that $\gamma_R(G)\leq8n/11$ when $\delta(G)\geq2$ and $n\geq9$, and this is sharp.

A graph is $(7,2)$-edge-choosable if, for every assignment of lists of size 7 to the edges, it is possible to choose 2 colors for each edge from its list so that no color is chosen for two incident edges. We show that every 3-edge-colorable graph is $(7,2)$-edge-choosable and also that many non-3-edge-colorable 3-regular graphs are $(7,2)$-edge-choosable.

In a bipartite graph G, a set $S\subseteq V(G)$ is deficient if $|N(S)|<|S|$. A matching M (with vertex set U) is k-suitable if $G-U$ has no deficient set of size less than k. Let $f_k(d)$ be the largest r such that in the d-dimensional hypercube $Q_d$ every k-suitable matching with at most r edges extends to a perfect matching. We generalize results of Limaye and Sarvate by proving that $f_k(d)=k(d-k)+\binom{k-1}{2}$ for $k\leq d-3$. To this end we prove lower bounds on the sizes of neighborhoods of vertex sets in $Q_d$. We also prove that every induced matching in $Q_d$ extends to a perfect matching.

A p-page embedding of a graph G is a vertex-ordering $\pi$ of $V(G)$ (along the “spine” of a book) and an assignment of edges to p half-planes (called “pages”) such that no page contains crossing edges (alternating endpoints) relative to $\pi$. The pagenumber of G is the least p such that G has a p-page embedding. We disprove a conjecture of Ganley and Heath by showing that when $k\geq3$, there are k-trees that do not embed in k pages. We also present an algorithm that produces k-page embeddings for k-trees in a special class.

Given a partition of the vertices of a graph into two sets, a flip is a move of a vertex from its own set to the other, under the condition that it has more incident edges to vertices in its own set than in the other. Every sequence of flips eventually produces a bipartite subgraph capturing more than half of the edges in the graph. Each flip gains at least one edge. For an n-vertex loopless multigraph, we show that there is always a sequence of at most $n/2$ flips that cannot be extended, and we construct a graph having a sequence of $\frac2{25}(n^2+n-31)$ flips.

Let G be a connected graph with maximum degree k (other than a complete graph or odd cycle), let W be a precolored set of vertices in G inducing a subgraph F, and let D be the minimum distance in G between components of F. If the components of F are complete graphs and $D\ge 8$ (for $k\ge 4$) or $D\ge 10$ (for k = 3), then every proper k-coloring of F extends to a proper k-coloring of G. If the components of F are single vertices and $Dge 8$, and the vertices outside W are assigned color lists of size k, then every k-coloring of F extends to a proper coloring of G with the color on each vertex chosen from its list. These results are sharp.

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$.

Given a graph $G=(V,\cal E)$, we want to find the vertex sets of the components of an unknown subgraph F=(V,E) of G such that $E \subseteq \cal E$. We learn about F by sending an oracle a query set $S \subseteq V$, and the oracle tells us the vertices connected to S in F. The objective is to use the minimum number of queries to partition the vertex set V into components of F. In electronic circuit design, the problem is also known as structural diagnosis of wiring networks.

Let G=(V,E) be a connected graph. A connected dominating set $S \subset V$ is a dominating set that induces a connected subgraph of G. The connected domination number of G, denoted $\gamma_c(G)$, is the minimum cardinality of a connected dominating set. Alternatively, $|V|-\gamma_c(G)$ is the maximum number of leaves in a spanning tree of G. Let $\delta$ denote the minimum degree of G. We prove that $\gamma_c(G) \leq |V| \frac{\ln(\delta+1)}{\delta+1}(1+o_\delta(1))$. Two algorithms that construct a set this good are presented. One is a sequential polynomial time algorithm, while the other is a randomized parallel algorithm in RNC.

Subsequent to the publication of this article in SIAM J. Discrete Math., 12 (1999), pp. 307--316, an error in one of the authors' affiliations was discovered. The correct affiliation follows: Tao Jiang, Department of Mathematics, University of Illinois, Urbana, IL 61801-2975 ([email protected]). Due to the serious nature of this mistake, a sticker containing the correct affiliation was printed and mailed to all print subscribers. This sticker should be placed over the footnotes on page 307 of volume 12 (1999), issue 3. A corrected version of the electronic file was posted to http://epubs.siam.org/sam-bin/dbq/article/33075 on December 13, 1999. SIAM sincerely regrets this error.

We want to find the vertex sets of components of a graph G with a known vertex set V and unknown edge set E. We learn about G by sending an oracle a query set $S \subseteq V$\hspace*{-1pt}, and the oracle tells us the vertices connected to S. The objective is to use the minimum number of queries to partition the vertex set into components. The problem is also known as interconnect diagnosis of wiring networks in VLSI. We present a deterministic algorithm using O(min{k, lg n}) queries and a randomized algorithm using expected O(min{k,lg k + lg lg n}) queries, where n is the number of vertices and k is the number of components. We also prove matching lower bounds.

The edge-bandwidth of a graph is the minimum, over all labelings of the edges with distinct integers, of the maximum difference between labels of two incident edges. We prove that edge-bandwidth is at least as large as bandwidth for every graph, with equality for certain caterpillars. We obtain sharp or nearly sharp bounds on the change in edge-bandwidth under addition, subdivision, or contraction of edges. We compute edge-bandwidth for K n , K n,n , caterpillars, and some theta graphs.

A multiple-interval representation of a simple graph G assigns each vertex a union of disjoint real intervals so that vertices are adjacent if and only if their assigned sets intersect. The total interval number$I(G)$ is the minimum of the total number of intervals used in such a representation of G. For triangle-free graphs, $I(G) = | E(G) |+t(G)$, where $t(G)$ is the minimum number of pairwise edge-disjoint trails that together contain an endpoint of each edge. This yields the NP-completeness of testing $I(G) = | E(G) | + 1$ (even for triangle-free 3-regular planar graphs) and an alternative proof that HAMILTONIAN CYCLE is NP-complete for line graphs. It also yields a linear-time algorithm to compute $I(G)$ for trees and a characterization of the trees requiring $| E(G) | + t$ intervals for fixed t. Further corollaries include the Aigner-Andreae bound of $I(G) \leq \lfloor {(5n - 3)/4} \rfloor $ for n-vertex trees (achieved by subdividing every edge of a star), a characterization of the extremal trees, and a shorter proof of the extremal bound $\lfloor {(5m + 2)/4} \rfloor $ for connected graphs.

This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T and the edge player chooses an edge e. The payoff to the edge player is $\textit{cost} (T, e)$, defined as follows: If e lies in the tree T then $\textit{cost}(T, e) = 0$; if e does not lie in the tree then $\textit{cost}(T, e) = cycle(T, e)/w(e)$, where $w(e)$ is the weight of edge e and $\textit{cycle}(T, e)$ is the weight of the unique cycle formed when edge e is added to the tree T. The main result is that the value of the game on any n-vertex graph is bounded above by $\exp(O(\sqrt{\log n \log \log n}))$. It is conjectured that the value of the game is $O(\log n)$. The game arises in connection with the k-server problem on a road network; i.e., a metric space that can be represented as a multigraph G in which each edge e represents a road of length $w(e)$. It is shown that, if the value of the game on G is $\textit{Val}(G, w)$, then there is a randomized strategy that achieves a competitive ratio of $k(1 + \textit{Val}(G, w))$ against any oblivious adversary. Thus, on any n-vertex road network, there is a randomized algorithm for the k-server problem that is $k \cdot \exp(O(\sqrt{\log n \log \log n}))$ competitive against oblivious adversaries. At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. Specifically, for any n-vertex weighted, connected multigraph, the algorithm constructs a spanning tree T such that the average, over all edges e, of $\textit{cost}(T, e)$ is less than or equal to $\exp(O(\sqrt{\log n \log \log n}))$. This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph.

A connected graph having large minimum vertex degree must have a spanning tree with many leaves. In particular, let $l( n,k )$ be the maximum integer m such that every connected n-vertex graph with minimum degree at least k has a spanning tree with at least m leaves. Then $l( n,3 )\geqq n/4 + 2, l( n,4 )\geqq ( 2n + 8 )/5,$ and $l( n,k )\leqq n - 3\lfloor n/( k + 1 ) \rfloor + 2$ for all k. The lower bounds are proved by an algorithm that constructs a spanning tree with at least the desired number of leaves. Finally, $l( n,k )\geqq ( 1 - b \ln k/k )n$ for large k, again proved algorithmically, where b is any constant exceeding 2.5.

The problem of minimizing the number of service ports of a central facility which serves a number of users subject to some constraints is addressed. At any time, a set of at most s users may want to use the facility, and one user can be connected to each port at a given time. It is assumed that there are direct communication links from users to service ports, with at most d links incident at a single service port. This problem maps to the graph-theoretic problem of minimizing the number of outputs of a bipartite graph with n inputs, such the degree of each output node is at most d and every set of k>

Two duality theorems are proved about the direct product of two partial orders. First, the size of the largest unichain (a chain fixed in one coordinate) equals the smallest number of semian-tichains (collections of elements in which no pair are comparable if they agree in either coordinate) needed to cover the elements of the product order. With analogous definitions, the size of a largest uniantichain equals the size of a smallest semichain covering.