A branch-and-price-and-cut method for computing an optimal bramble

Given an undirected graph, a bramble is a set of connected subgraphs (called bramble elements) such that every pair of subgraphs either contains a common node, or such that an edge $(i,j)$ exists with node $i$ belonging to one subgraph and node $j$ belonging to the other. In this paper we examine the problem of finding the bramble number of a graph, along with a set of bramble elements that yields this number. The bramble number is the largest cardinality of a minimum hitting set over all bramble elements on this graph. A graph with bramble number $k$ has a treewidth of $k-1$. We provide a branch-and-price-and-cut method that generates columns corresponding to bramble elements, and rows corresponding to hitting sets. We then examine the computational efficacy of our algorithm on a randomly generated data set.     

Bounding the distance among longest paths in a connected graph

It is easy to see that in a connected graph any $2$ longest paths have a vertex in common. For $k\ge 7$, Skupień in 1966 obtained a connected graph in which some $k$ longest paths have no common vertex, but every $k?1$ longest paths have a common vertex. It is not known whether every $3$ longest paths in a connected graph have a common vertex and similarly for 4, 5, and $6$ longest path. Fujita et al. in 2015 give an upper bound on distance among $3$ longest paths in a connected graph. In this paper we give a similar upper bound on distance between $4$ longest paths and also for $k$ longest paths, in general.     

Max-cut and extendability of matchings in distance-regular graphs

A connected graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is $1$-extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions.In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter $D\ge 3$ are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency $k\ge 3$ that depend on $k$, $\lambda$ and $\mu$, where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency $k$ grows linearly in $k$. We conjecture that the extendability of a distance-regular graph of even order and valency $k$ is at least $\lceil k/2\rceil -1$ and we prove this fact for bipartite distance-regular graphs.In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters.     

Graph coloring and Graham’s greatest common divisor problem

In this paper we introduce and study two graph coloring problems and relate them to some deep number-theoretic problems. For a fixed positive integer $k$ consider a graph $B_k$ whose vertex set is the set of all positive integers with two vertices $a,b$ joined by an edge whenever the two numbers $a∕gcd(a,b)$ and $b∕gcd(a,b)$ are both at most $k$. We conjecture that the chromatic number of every such graph $B_k$ is equal to $k$. This would generalize the greatest common divisor problem of Graham from 1970; in graph-theoretic terminology it states that the clique number of $B_k$ is equal to $k$. Our conjecture is connected to integer lattice tilings and partial Latin squares completions.     

On Eulerian orientations of even-degree hypercubes

It is well known that every Eulerian orientation of an Eulerian $2k$-edge connected (undirected) graph is strongly $k$-edge connected. A long-standing goal in the area is to obtain analogous results for other types of connectivity, such as node connectivity. We show that every Eulerian orientation of the hypercube of degree $2k$ is strongly $k$-node connected.     

On the maximum size of connected hypergraphs without a path of given length

In this note we asymptotically determine the maximum number of hyperedges possible in an $r$-uniform, connected $n$-vertex hypergraph without a Berge path of length $k$, as $n$ and $k$ tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.     

Locating a robber with multiple probes

We consider a game in which a cop searches for a moving robber on a connected graph using distance probes, which is a slight variation on one introduced by Seager (2012). Carragher, Choi, Delcourt, Erickson and West showed that for any $n$-vertex graph $G$ there is a winning strategy for the cop on the graph $G^{1∕m}$ obtained by replacing each edge of $G$ by a path of length $m$, if $m\ge n$ (Carragher et al., 2012). The present authors showed that, for all but a few small values of $n$, this bound may be improved to $m\ge n∕2$, which is best possible (Haslegrave et al., 2016). In this paper we consider the natural extension in which the cop probes a set of $k$ vertices, rather than a single vertex, at each turn. We consider the relationship between the value of $k$ required to ensure victory on the original graph with the length of subdivisions required to ensure victory with $k=1$. We give an asymptotically best-possible linear bound in one direction, but show that in the other direction no subexponential bound holds. We also give a bound on the value of $k$ for which the cop has a winning strategy on any (possibly infinite) connected graph of maximum degree $\Delta$, which is best possible up to a factor of $(1?o\left(1\right))$.     

Randomly Pk-decomposable graphs

A graph $G$ is $H$-decomposable if it can be expressed as an edge-disjoint union of subgraphs, each subgraph isomorphic to $H$. If $G$ has the additional property that every $H$-decomposable subgraph of $G$ is part of an $H$-decomposition of $G$, then $G$ is randomly $H$-decomposable. Using computer assistance, we provide in this paper a characterization of randomly path-decomposable graphs for paths of length 11 or less. We also prove the following two results: (1) With one small exception, randomly $P_k$-decomposable graphs with a vertex of odd degree do not contain a $P_{k+1}$-subgraph, (2) When the edges of a $P_k$-subgraph are deleted from a connected randomly $P_k$-decomposable graph, the resulting graph has at most one nontrivial component.     

An improved bound for disjoint directed cycles

We show that every directed graph with minimum out-degree at least $18k$ contains at least $k$ vertex disjoint cycles. This is an improvement over the result of Alon who showed this result for digraphs of minimum out-degree at least $64k$. The main benefit of the argument is that getting better results for small values of $k$ allows for further improvements to the constant.     

Equitable defective coloring of sparse planar graphs

A graph has an equitable, defective $k$-coloring (an ED-$k$-coloring) if there is a $k$-coloring of $V\left(G\right)$ that is defective (every vertex shares the same color with at most one neighbor) and equitable (the sizes of all color classes differ by at most one). A graph may have an ED-$k$-coloring, but no ED-$(k+1)$-coloring. In this paper, we prove that planar graphs with minimum degree at least $2$ and girth at least $10$ are ED-$k$-colorable for any integer $k\ge 3$. The proof uses the method of discharging. We are able to simplify the normally lengthy task of enumerating forbidden substructures by using Hall’s Theorem, an unusual approach.     

Packing chromatic number of cubic graphs

A packing$k$-coloring of a graph $G$ is a partition of $V\left(G\right)$ into sets $V_1,\dots ,V_k$ such that for each $1\le i\le k$ the distance between any two distinct $x,y\in V_i$ is at least $i+1$. The packing chromatic number, ${\chi }_p\left(G\right)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. Sloper showed that there are $4$-regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed $k$ and $g\ge 2k+2$, almost every $n$-vertex cubic graph of girth at least $g$ has the packing chromatic number greater than $k$.     

The structure of 4-γ-critical graphs with a cut vertex

Let $\gamma \left(G\right)$ denote the minimum cardinality of a dominating set for $G$. A graph $G$ is said to be $k$-$\gamma$-critical if $\gamma \left(G\right)=k$, but $\gamma (G+e)<k$ for each edge $e\in E\left(\overline{G}\right)$. In this paper, we provide the structure of 4-$\gamma$-critical connected graphs with a cut vertex. We establish that such graphs of even order contain a perfect matching. This result partially resolves a problem posed by Sumner and Wojcicka in 1998. They asked whether every $k$-$\gamma$-critical graph of even order contains a perfect matching for $k\ge 4$.     

Pentavalent symmetric graphs admitting transitive non-abelian characteristically simple groups

Let $\Gamma$ be a graph and let $G$ be a group of automorphisms of $\Gamma$. The graph $\Gamma$ is called $G$-normal if $G$ is normal in the automorphism group of $\Gamma$. Let $T$ be a finite non-abelian simple group and let $G=T^l$ with $l\ge 1$. In this paper we prove that if every connected pentavalent symmetric $T$-vertex-transitive graph is $T$-normal, then every connected pentavalent symmetric $G$-vertex-transitive graph is $G$-normal. This result, among others, implies that every connected pentavalent symmetric $G$-vertex-transitive graph is $G$-normal except $T$ is one of 57 simple groups. Furthermore, every connected pentavalent symmetric $G$-regular graph is $G$-normal except $T$ is one of 20 simple groups, and every connected pentavalent $G$-symmetric graph is $G$-normal except $T$ is one of 17 simple groups.     

Proper colouring Painter–Builder game

We consider the following two-player game, parametrised by positive integers $n$ and $k$. The game is played between Painter and Builder, alternately taking turns, with Painter moving first. The game starts with the empty graph on $n$ vertices. In each round Painter colours a vertex of her choice by one of the $k$ colours and Builder adds an edge between two previously unconnected vertices. Both players must adhere to the restriction that the game graph is properly $k$-coloured. The game ends if either all $n$ vertices have been coloured, or Painter has no legal move. In the former case, Painter wins the game; in the latter one, Builder is the winner. We prove that the minimal number of colours $k=k\left(n\right)$ allowing Painter’s win is of logarithmic order in the number of vertices $n$. Biased versions of the game are also considered.