Search

We study a competitive optimization version of $\alpha'(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)=\alpha'(G)$ that is preserved under cartesian product. In general, $\Max(G)\ge \frac23\alpha'(G)$, with equality for many split graphs, while $\Max(G)\ge\frac34\alpha'(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$., Comment: 16 pages; this version improves explanations at a number of points and adds a few more examples

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 $\sigma(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 \sigma(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, $\sigma(G,m,r)\le\gamma(G)\floor{r/m}$, where $\gamma(G)$ is the domination number; this bound is nearly sharp when $\gamma(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 $\sigma(G,m,r)$ is near the trivial upper bound when $rc'\ln n$. For the hypercube $Q_d$ with $d\ge r$, we have $\sigma(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 $\sigma(G,m,r)$ is approximately $\frac{k}{k-1}\frac{r}{m}$ when $k\ge m$. For $k=2$, we have $\sigma(G,2,r)=\bigl\lceil{\frac{\floor{7r/2}-3}5}\bigr\rceil$ and $\sigma(G,3,r)=\floor{r/2}$, and in general $\frac{3r}{2m}-3\le \sigma(G,m,r)\le\frac{(1+1/\sqrt3)r}{m}$., Comment: 34 pages, 2 figures. The most important changes in this revision are improvements of the results on hypercubes and random graphs. The proof of the previous hypercube result has been deleted, but the statement remains because it is stronger for m<52. In the random graph section we added a spy-strategy result

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}, Comment: 9 pages

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., Comment: 14 pages, 1 figure

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 $\delta(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)., Comment: 21 pages

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., Comment: 12 pages, 1 figure

An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)-biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)-biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3-valent vertices and lengths in {2,4,6,8}. We provide sufficient conditions for the existence of such a subgraph., Comment: 11 pages, 2 figures

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., Comment: 7 pages, 2 figures

In a graph whose edges are colored, a parity walk is a walk that uses each color an even number of times. The parity edge chromatic number p(G) of a graph G is the least k so that there is a coloring of E(G) using k colors that does not contain a parity path. The strong parity edge chromatic number p'(G) of G is the least k so that there is a coloring of E(G) using k colors with the property that every parity walk is closed. Our main result is to determine p'(K_n). Specifically, if m is the least power of two that is as large as n, then p'(K_n) has value m - 1. As a corollary, we strengthen a special case of an old result of Daykin and Lovasz. Other results include determining p(G) and p'(G) whenever G is a path, cycle, or of the form K_{2,n}, and an upper bound on p'(G) for the case that G is a complete bipartite graph. We conclude with a sample of open problems., Comment: 23 pages, 0 figures

Given graphs H_1,...,H_k, we study the minimum order of a graph G such that for each i, the induced copies of H_i in G cover V(G). We prove a general upper bound of twice the sum of the numbers m_i, where m_i is one less than the order of H_i. When k=2 and one graph is an independent set of size n, we determine the optimum within a constant. When k=2 and the graphs are a star and an independent set, we determine the answer exactly., Comment: 10 pages, 3 figures

The chromatic sum of a graph is the smallest sum of colors among all proper colorings with natural numbers. The strength is the minimum number of colors needed to achieve the chromatic sum. We construct for each positive integer k a tree with strength k that has maximum degree only 2k-2. The result is best possible., Comment: 5 pages, 1 figure

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 cliques, bicliques, caterpillars, and some theta graphs., Comment: 12 pages

A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations., Comment: 2 pages

The leafage of a digraph is the minimum number of leaves in a host tree in which it has a subtree intersection representation. We discuss bounds on the leafage in terms of other parameters (including Ferrers dimension), obtaining a string of sharp inequalities., Comment: 12 pages, 3 included figures

In a directed graph, the imbalance of a vertex is its outdegree minus its indegree. We characterize the sequences that are realizable as the sequence of imbalances of a simple directed graph. Moreover, a realization of a realizable sequence can be produced by a greedy algorithm., Comment: 5 pages

Erd\H{o}s proved that there are graphs with arbitrarily large girth and chromatic number. We study the extension of this for generalized chromatic numbers., Comment: 6 pages

The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - (1/2) lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal sets and structural properties of chordal graphs., Comment: 19 pages, 3 figures

Let S_m denote the m-vertex simple digraph formed by m-1 edges with a common tail. Let f(m) denote the minimum n such that every n-vertex tournament has a spanning subgraph consisting of n/m disjoint copies of S_m. We prove that m lg m - m lg lg m <= f(m) <= 4m^2 - 6m for sufficiently large m., Comment: 5 pages, 1 figure

The concept of coreflexive set is introduced to study the structure of digraphs. New characterizations of line digraphs and nth-order line digraphs are given. Coreflexive sets also lead to another natural way of forming an intersection digraph from a given digraph., Comment: 8 pages, 3 figures

The bandwidth of a graph G is the minimum of the maximum difference between adjacent labels when the vertices have distinct integer labels. We provide a polynomial algorithm to produce an optimal bandwidth labeling for graphs in a special class of block graphs (graphs in which every block is a clique), namely those where deleting the vertices of degree one produces a path of cliques. The result is best possible in various ways. Furthermore, for two classes of graphs that are ``almost'' caterpillars, the bandwidth problem is NP-complete., Comment: 14 pages, 9 included figures. Note: figures did not appear in original upload; resubmission corrects this

We introduce a combinatorial enumeration problem that is solved using generalized Catalan numbers. We also study generalizations of the Cycle Lemma beyond the computation of the generalized Catalan numbers., Comment: 14 pages, 8 included figures