BZPEER

preprint2020arXiv

On reconstruction of graphs from the multiset of subgraphs obtained by deleting $\ell$ vertices

The Reconstruction Conjecture of Ulam asserts that, for $n\geq 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 integer $\ell$ there exists $M_\ell$ (with $M_1=3$ ) such that when $n\geq M_\ell$ every $n$ -vertex graph is determined by the multiset of its induced subgraphs with $n-\ell$ vertices.

preprint2020arXiv

The Number of Perfect Matchings in Möbius Ladders and Prisms

The 1970s conjecture of Lovász and Plummer that the number of perfect matchings in any $3$ -regular graph is exponential in the number of vertices was proved in 2011 by Esperet, Kardoš, King, Král', and Norine. We give the exact formula for the number of perfect matchings in two families of $3$ -regular graphs. In the graph consisting of a $2n$ -cycle with diametric chords (also known as the Möbius ladder $M_n$ and a Harary graph) and in the cartesian product of the cycle $C_n$ with an edge (called the cycle prism), the number of matchings is the sum of the Fibonacci numbers $F_{n-1}$ and $F_{n+1}$ , plus two more for the Möbius ladder when $n$ is odd and for the cycle prism when $n$ is even.

preprint2018arXiv

Ramsey Numbers of Interval 2-chromatic Ordered Graphs

An ordered graph $G$ is a graph together with a specified linear ordering on the vertices, and its interval chromatic number is the minimum number of independent sets consisting of consecutive vertices that are needed to partition the vertex set. The $t$ -color Ramsey number $R_t(G)$ of an ordered graph $G$ is the minimum number of vertices of an ordered complete graph such that every edge-coloring from a set of $t$ colors contains a monochromatic copy of $G$ such that the copy of $G$ preserves the original ordering on $G$ . An ordered graph is $k$ -ichromatic if it has interval chromatic number $k$ . We obtain lower bounds linear in the number of vertices for the Ramsey numbers of certain classes of 2-ichromatic ordered graphs. We also determine the exact value of the $t$ -color Ramsey number for two families of 2-ichromatic ordered graphs, and we prove a linear upper bound for a class of 2-ichromatic ordered graphs.

preprint2016arXiv

Fractional and Circular Separation Dimension of Graphs

The separation dimension of a graph $G$ , written $π(G)$ , is the minimum number of linear orderings of $V(G)$ such that every two nonincident edges are "separated" in some ordering, meaning that both endpoints of one edge appear before both endpoints of the other. We introduce the fractional separation dimension $π_f(G)$ , which is the minimum of $a/b$ such that some $a$ linear orderings (repetition allowed) separate every two nonincident edges at least $b$ times. In contrast to separation dimension, fractional separation dimension is bounded: always $π_f(G)\le 3$ , with equality if and only if $G$ contains $K_4$ . There is no stronger bound even for bipartite graphs, since $π_f(K_{m,m})=π_f(K_{m+1,m})=\frac{3m}{m+1}$ . We also compute $π_f(G)$ for cycles and some complete tripartite graphs. We show that $π_f(G)<\sqrt 2$ when $G$ is a tree and present a sequence of trees on which the value tends to $4/3$ . Finally, we consider analogous problems for circular orderings, where pairs of nonincident edges are separated unless their endpoints alternate. Let $π^\circ(G)$ be the number of circular orderings needed to separate all pairs and $π_f^\circ(G)$ be the fractional version. Among our results: (1) $π^\circ(G)=1$ if and only $G$ is outerplanar. (2) $π^\circ(G)\le2$ when $G$ is bipartite. (3) $π^\circ(K_n)\ge\log_2\log_3(n-1)$ . (4) $π_f^\circ(G)\le\frac{3}{2}$ , with equality if and only if $K_4\subseteq G$ . (5) $π_f^\circ(K_{m,m})=\frac{3m-3}{2m-1}$ .

preprint2016arXiv

Reconstruction from $k$ -decks for graphs with maximum degree 2

The $k$ -deck of a graph is its multiset of induced subgraphs on $k$ vertices. We prove that $n$ -vertex graphs with maximum degree $2$ have the same $k$ -decks if each cycle has at least $k+1$ vertices, each path component has at least $k-1$ vertices, and the number of edges is the same. Using this for lower bounds, we obtain for each graph with maximum degree at most $2$ the least $k$ such that it is determined by its $k$ -deck. For the $n$ -vertex cycle this value is $\lfloor n/2 \rfloor$ , and for the $n$ -vertex path it is $\lfloor n/2 \rfloor+1$ . Also, the least $k$ such that the $k$ -deck of an $n$ -vertex graph always determines whether it is connected is at least $\lfloor n/2 \rfloor +1$ .

preprint2016arXiv

Spanning Trees in 2-trees

A spanning tree of a graph $G$ is a connected acyclic spanning subgraph of $G$ . We consider enumeration of spanning trees when $G$ is a $2$ -tree, meaning that $G$ is obtained from one edge by iteratively adding a vertex whose neighborhood consists of two adjacent vertices. We use this construction order both to inductively list the spanning trees without repetition and to give bounds on the number of them. We determine the $n$ -vertex $2$ -trees having the most and the fewest spanning trees. The $2$ -tree with the fewest is unique; it has $n-2$ vertices of degree $2$ and has $n2^{n-3}$ spanning trees. Those with the most are all those having exactly two vertices of degree $2$ , and their number of spanning trees is the Fibonacci number $F_{2n-2}$ .

preprint2016arXiv

The vulnerability of the diameter of enhanced hypercubes

For an interconnection network $G$ , the {\it $ω$ -wide diameter} $d_ω(G)$ is the least $\ell$ such that any two vertices are joined by $ω$ internally-disjoint paths of length at most $\ell$ , and the {\it $(ω-1)$ -fault diameter} $D_ω(G)$ is the maximum diameter of a subgraph obtained by deleting fewer than $ω$ vertices of $G$ . The enhanced hypercube $Q_{n,k}$ is a variant of the well-known hypercube. Yang, Chang, Pai, and Chan gave an upper bound for $d_{n+1}(Q_{n,k})$ and $D_{n+1}(Q_{n,k})$ and posed the problem of finding the wide diameters and fault diameters of $Q_{n,k}$ . By constructing internally disjoint paths between any two vertices in the enhanced hypercube, for $n\ge3$ and $2\le k\le n$ we prove $D_ω(Q_{n,k})=d_ω(Q_{n,k})=\begin{cases} d(Q_{n,k}) & \textrm{for $1 \leq ω< n-\lfloor\frac{k}{2}\rfloor$;}\\ d(Q_{n,k})+1 & \textrm{for $n-\lfloor\frac{k}{2}\rfloor \leq ω\leq n+1$.} \end{cases}$ where $d(Q_{n,k})$ is the diameter of $Q_{n,k}$ . These results mean that interconnection networks modelled by enhanced hypercubes are extremely robust.

preprint2016arXiv

To catch a falling robber

We consider a Cops-and-Robber game played on the subsets of an $n$ -set. The robber starts at the full set; the cops start at the empty set. On each turn, the robber moves down one level by discarding an element, and each cop moves up one level by gaining an element. The question is how many cops are needed to ensure catching the robber when the robber reaches the middle level. Aaron Hill posed the problem and provided a lower bound of $2^{n/2}$ for even $n$ and $\binom{n}{\lceil n/2 \rceil}2^{-\lfloor n/2 \rfloor}$ for odd $n$ . We prove an upper bound (for all $n$ ) that is within a factor of $O(\ln n)$ times this lower bound.

preprint2015arXiv

Coloring, sparseness, and girth

An $r$ -augmented tree is a rooted tree plus $r$ edges added from each leaf to ancestors. For $d,g,r\in\mathbb{N}$ , we construct a bipartite $r$ -augmented complete $d$ -ary tree having girth at least $g$ . The height of such trees must grow extremely rapidly in terms of the girth. Using the resulting graphs, we construct sparse non- $k$ -choosable bipartite graphs, showing that maximum average degree at most $2(k-1)$ is a sharp sufficient condition for $k$ -choosability in bipartite graphs, even when requiring large girth. We also give a new simple construction of non- $k$ -colorable graphs and hypergraphs with any girth $g$ .

preprint2015arXiv

Uniquely cycle-saturated graphs

Given a graph $F$ , a graph $G$ is {\it uniquely $F$ -saturated} if $F$ is not a subgraph of $G$ and adding any edge of the complement to $G$ completes exactly one copy of $F$ . In this paper we study uniquely $C_t$ -saturated graphs. We prove the following: (1) a graph is uniquely $C_5$ -saturated if and only if it is a friendship graph. (2) There are no uniquely $C_6$ -saturated graphs or uniquely $C_7$ -saturated graphs. (3) For $t\ge6$ , there are only finitely many uniquely $C_t$ -saturated graphs (we conjecture that in fact there are none).

preprint2014arXiv

Beyond Ohba's Conjecture: A bound on the choice number of $k$ -chromatic graphs with $n$ vertices

Let $\text{ch}(G)$ denote the choice number of a graph $G$ (also called "list chromatic number" or "choosability" of $G$ ). Noel, Reed, and Wu proved the conjecture of Ohba that $\text{ch}(G)=χ(G)$ when $|V(G)|\le 2χ(G)+1$ . We extend this to a general upper bound: $\text{ch}(G)\le \max\{χ(G),\lceil({|V(G)|+χ(G)-1})/{3}\rceil\}$ . Our result is sharp for $|V(G)|\le 3χ(G)$ using Ohba's examples, and it improves the best-known upper bound for $\text{ch}(K_{4,\dots,4})$ .

preprint2014arXiv

The Game Saturation Number of a Graph

Given a family ${\mathcal F}$ and a host graph $H$ , a graph $G\subseteq H$ is ${\mathcal F}$ -saturated relative to $H$ if no subgraph of $G$ lies in ${\mathcal F}$ but adding any edge from $E(H)-E(G)$ to $G$ creates such a subgraph. In the ${\mathcal F}$ -saturation game on $H$ , players Max and Min alternately add edges of $H$ to $G$ , avoiding subgraphs in ${\mathcal F}$ , until $G$ becomes ${\mathcal F}$ -saturated relative to $H$ . They aim to maximize or minimize the length of the game, respectively; $\textrm{sat}_g({\mathcal F};H)$ denotes the length under optimal play (when Max starts). Let ${\mathcal O}$ denote the family of all odd cycles and ${\mathcal T}$ the family of $n$ -vertex trees, and write $F$ for ${\mathcal F}$ when ${\mathcal F}=\{F\}$ . Our results include $\textrm{sat}_g({\mathcal O};K_{2k})=k^2$ , $\textrm{sat}_g({\mathcal T};K_n)=\binom{n-2}{2}+1$ for $n\ge6$ , $\textrm{sat}_g(K_{1,3};K_n)=2\lfloor n/2 \rfloor$ for $n\ge8$ , $\textrm{sat}_g(K_{1,r+1};K_n)=\frac{rn}{2}-\frac{r^2}{8}+O(1)$ , and $|\textrm{sat}_g(P_4;K_n)-(4n-1)/5|\le 1$ . We also determine $\textrm{sat}_g(P_4;K_{m,n})$ ; with $m\ge n$ , it is $n$ when $n$ is even, $m$ when $n$ is odd and $m$ is even, and $m+\lfloor n/2 \rfloor$ when $mn$ is odd. Finally, we prove the lower bound $\textrm{sat}_g(C_4;K_{n,n})\ge\frac{1}{10.4}n^{13/12}-O(n^{35/36})$ . The results are very similar when Min plays first, except for the $P_4$ -saturation game on $K_{m,n}$ .

preprint2013arXiv

1,2,3-Conjecture and 1,2-Conjecture for Sparse Graphs

We apply the Discharging Method to prove the 1,2,3-Conjecture and the 1,2-Conjecture for graphs with maximum average degree less than 8/3. Stronger results on these conjectures have been proved, but this is the first application of discharging to them, and the structure theorems and reducibility results are of independent interest.

preprint2012arXiv

Game matching number of graphs

We study a competitive optimization version of $α'(G)$ , the maximum size of a matching in a graph $G$ . Players alternate adding edges of $G$ to a matching until it becomes a maximal matching. One player (Max) wants that matching to be large; the other (Min) wants it to be small. The resulting sizes under optimal play when Max or Min starts are denoted $\Max(G)$ and $\Min(G)$, respectively. We show that always $|\Max(G)-\Min(G)|\le 1$. We obtain a sufficient condition for $\Max(G)=α'(G)$ that is preserved under cartesian product. In general, $\Max(G)\ge \frac23α'(G)$, with equality for many split graphs, while $\Max(G)\ge\frac34α'(G)$ when $G$ is a forest. Whenever $G$ is a 3-regular $n$ -vertex connected graph, $\Max(G) \ge n/3$, and there are such examples with $\Max(G)\le 7n/18$. For an $n$ -vertex path or cycle, the answer is roughly $n/7$ .

preprint2012arXiv

Revolutionaries and spies: Spy-good and spy-bad graphs

We study a game on a graph $G$ played by $r$ {\it revolutionaries} and $s$ {\it spies}. Initially, revolutionaries and then spies occupy vertices. In each subsequent round, each revolutionary may move to a neighboring vertex or not move, and then each spy has the same option. The revolutionaries win if $m$ of them meet at some vertex having no spy (at the end of a round); the spies win if they can avoid this forever. Let $σ(G,m,r)$ denote the minimum number of spies needed to win. To avoid degenerate cases, assume $|V(G)|\ge r-m+1\ge\floor{r/m}\ge 1$. The easy bounds are then $\floor{r/m}\le σ(G,m,r)\le r-m+1$. We prove that the lower bound is sharp when $G$ has a rooted spanning tree $T$ such that every edge of $G$ not in $T$ joins two vertices having the same parent in $T$ . As a consequence, $σ(G,m,r)\leγ(G)\floor{r/m}$, where $γ(G)$ is the domination number; this bound is nearly sharp when $γ(G)\le m$ . For the random graph with constant edge-probability $p$ , we obtain constants $c$ and $c'$ (depending on $m$ and $p$ ) such that $σ(G,m,r)$ is near the trivial upper bound when $r<c\ln n$ and at most $c'$ times the trivial lower bound when $r>c'\ln n$ . For the hypercube $Q_d$ with $d\ge r$ , we have $σ(G,m,r)=r-m+1$ when $m=2$ , and for $m\ge 3$ at least $r-39m$ spies are needed. For complete $k$ -partite graphs with partite sets of size at least $2r$ , the leading term in $σ(G,m,r)$ is approximately $\frac{k}{k-1}\frac{r}{m}$ when $k\ge m$ . For $k=2$ , we have $σ(G,2,r)=\bigl\lceil{\frac{\floor{7r/2}-3}5}\bigr\rceil$ and $σ(G,3,r)=\floor{r/2}$, and in general $\frac{3r}{2m}-3\le σ(G,m,r)\le\frac{(1+1/\sqrt3)r}{m}$ .

preprint2011arXiv

Chain-making games in grid-like posets

We study the Maker-Breaker game on the hypergraph of chains of fixed size in a poset. In a product of chains, the maximum size of a chain that Maker can guarantee building is $k-\lfloor r/2\rfloor$ , where $k$ is the maximum size of a chain in the product, and $r$ is the maximum size of a factor chain. We also study a variant in which Maker must follow the chain in order, called the {\it Walker-Blocker game}. In the poset consisting of the bottom $k$ levels of the product of $d$ arbitrarily long chains, Walker can guarantee a chain that hits all levels if $d\ge14$ ; this result uses a solution to Conway's Angel-Devil game. When d=2, the maximum that Walker can guarantee is only 2/3 of the levels, and 2/3 is asymptotically achievable in the product of two equal chains.

preprint2011arXiv

Revolutionaries and spies on trees and unicyclic graphs

A team of $r$ {\it revolutionaries} and a team of $s$ {\it spies} play a game on a graph $G$ . Initially, revolutionaries and then spies take positions at vertices. In each subsequent round, each revolutionary may move to an adjacent vertex or not move, and then each spy has the same option. The revolutionaries want to hold an {\it unguarded meeting}, meaning $m$ revolutionaries at some vertex having no spy at the end of a round. To prevent this forever, trivially at least $\min\{|V(G)|,\FL{r/m}\}$ spies are needed. When $G$ is a tree, this many spies suffices. When $G$ is a unicyclic graph, $\min\{|V(G)|,\CL{r/m}\}$ spies suffice, and we characterize those unicyclic graphs where $\FL{r/m}+1$ spies are needed. \def\FL#1{\lfloor #1 \rfloor} \def\CL#1{\lceil #1 \rceil}

preprint2010arXiv

Overlap Number of Graphs

An {\it overlap representation} of a graph $G$ assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The {\it overlap number} $\ol(G)$ (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If $δ(G)\ge 2$ and $G\ne K_3$ , then $\ol(G)\le |E(G)|-1$, with equality when $G$ is connected and triangle-free and has no star-cutset. (3) If $G$ is an $n$ -vertex plane graph with $n\ge5$ , then $\ol(G)\le 2n-5$, with equality when every face has length 4 and there is no star-cutset. (4) If $G$ is an $n$ -vertex graph with $n\ge 14$ , then $\ol(G)\le \floor{n^2/4-n/2-1}$, and this is sharp (for even $n$ , equality holds when $G$ arises from $K_{n/2,n/2}$ by deleting a perfect matching).

preprint2008arXiv

Classes of 3-regular graphs that are (7, 2)-edge-choosable

A graph is (7, 2)-edge-choosable if, for every assignment of lists of size 7 to the edges, it is possible to choose two 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.

preprint2006arXiv

Short Proofs for Cut-and-Paste Sorting of Permutations

We consider the problem of determining the maximum number of moves required to sort a permutation of $[n]$ using cut-and-paste operations, in which a segment is cut out and then pasted into the remaining string, possibly reversed. We give short proofs that every permutation of $[n]$ can be transformed to the identity in at most $\flr{2n/3}$ such moves and that some permutations require at least $\flr{n/2}$ moves.

Douglas B. West

Research overview

Is this your work?

20 publications

On reconstruction of graphs from the multiset of subgraphs obtained by deleting $\ell$ vertices

The Number of Perfect Matchings in Möbius Ladders and Prisms

Ramsey Numbers of Interval 2-chromatic Ordered Graphs

Fractional and Circular Separation Dimension of Graphs

Reconstruction from $k$ -decks for graphs with maximum degree 2

Spanning Trees in 2-trees

The vulnerability of the diameter of enhanced hypercubes

To catch a falling robber

Coloring, sparseness, and girth

Uniquely cycle-saturated graphs

Beyond Ohba's Conjecture: A bound on the choice number of $k$ -chromatic graphs with $n$ vertices

The Game Saturation Number of a Graph

1,2,3-Conjecture and 1,2-Conjecture for Sparse Graphs

Game matching number of graphs

Revolutionaries and spies: Spy-good and spy-bad graphs

Chain-making games in grid-like posets

Revolutionaries and spies on trees and unicyclic graphs

Overlap Number of Graphs

Classes of 3-regular graphs that are (7, 2)-edge-choosable

Short Proofs for Cut-and-Paste Sorting of Permutations

See the researcher in context

Building this map preview

Douglas B. West

Research overview

Is this your work?

20 publications

On reconstruction of graphs from the multiset of subgraphs obtained by deleting ℓ\ellℓ vertices

The Number of Perfect Matchings in Möbius Ladders and Prisms

Ramsey Numbers of Interval 2-chromatic Ordered Graphs

Fractional and Circular Separation Dimension of Graphs

Reconstruction from kkk-decks for graphs with maximum degree 2

Spanning Trees in 2-trees

The vulnerability of the diameter of enhanced hypercubes

To catch a falling robber

Coloring, sparseness, and girth

Uniquely cycle-saturated graphs

Beyond Ohba's Conjecture: A bound on the choice number of kkk-chromatic graphs with nnn vertices

The Game Saturation Number of a Graph

1,2,3-Conjecture and 1,2-Conjecture for Sparse Graphs

Game matching number of graphs

Revolutionaries and spies: Spy-good and spy-bad graphs

Chain-making games in grid-like posets

Revolutionaries and spies on trees and unicyclic graphs

Overlap Number of Graphs

Classes of 3-regular graphs that are (7, 2)-edge-choosable

Short Proofs for Cut-and-Paste Sorting of Permutations

See the researcher in context

Building this map preview

On reconstruction of graphs from the multiset of subgraphs obtained by deleting $\ell$ vertices

Reconstruction from $k$ -decks for graphs with maximum degree 2

Beyond Ohba's Conjecture: A bound on the choice number of $k$ -chromatic graphs with $n$ vertices