BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Douglas B. West

Douglas B. West contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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).

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access