The NLC-width and clique-width for powers of graphs of bounded tree-width

The $k$-power graph of a graph $G$ is a graph with the same vertex set as $G$, in that two vertices are adjacent if and only if, there is a path between them in $G$ of length at most $k$. A $k$-tree-power graph is the $k$-power graph of a tree, a $k$-leaf-power graph is the subgraph of some $k$-tree-power graph induced by the leaves of the tree.We show that (1) every $k$-tree-power graph has NLC-width at most $k+2$ and clique-width at most $k+2+max\{?\frac{k}{2}??1,0\}$, (2) every $k$-leaf-power graph has NLC-width at most $k$ and clique-width at most $k+max\{?\frac{k}{2}??2,0\}$, and (3) every $k$-power graph of a graph of tree-width $l$ has NLC-width at most ${(k+1)}^{l+1}?1$, and clique-width at most $2?{(k+1)}^{l+1}?2$.     

Embeddings of rank-2 tori in algebraic groups

Let k be a field of characteristic different from 2 and 3. In this paper we study connected simple algebraic groups of type $A_2$, $G_2$ and $F_4$ defined over k, via their rank-2 k-tori. Simple, simply connected groups of type $A_2$ play a pivotal role in the study of exceptional groups and this aspect is brought out by the results in this paper. We refer to tori, which are maximal tori of $A_n$ type groups, as unitary tori. We discuss conditions necessary for a rank-2 unitary k-torus to embed in simple k-groups of type $A_2$, $G_2$ and $F_4$ in terms of the mod-2 Galois cohomological invariants attached with these groups. The results in this paper and our earlier paper ([6]) show that the mod-2 invariants of groups of type $G_2,F_4$ and $A_2$ are controlled by their k-subgroups of type $A_1$ and $A_2$ as well as the unitary k-tori embedded in them.     

An approximation algorithm for the Euclidean incremental median problem

In the incremental version of the $k$-median problem, we find a sequence of facility sets $F_1\subseteq F_2\subseteq \cdots \subseteq F_n$, where each $F_k$ contains at most $k$ facilities. This sequence is said to be $\delta$-competitive if the cost of each $F_k$ is at most $\delta$ times the optimum cost of $k$ facilities. The best deterministic (randomized) algorithm available for the metric space has a competitive ratio of $8$ ($7.656$). The best one for the one-dimensional problem finds a $5.828$-competitive sequence. We give a $7.076$-competitive solution for the high-dimensional Euclidean space.     

Bounds on the length of a game of Cops and Robbers

In the game of Cops and Robbers, a team of cops attempts to capture a robber on a graph $G$. All players occupy vertices of $G$. The game operates in rounds; in each round the cops move to neighboring vertices, after which the robber does the same. The minimum number of cops needed to guarantee capture of a robber on $G$ is the cop number of $G$, denoted $c\left(G\right)$, and the minimum number of rounds needed for them to do so is the capture time. It has long been known that the capture time of an $n$-vertex graph with cop number $k$ is $O\left(n^{k+1}\right)$. More recently, Bonato et al. (2009) and Gaven?iak (2010) showed that for $k=1$, this upper bound is not asymptotically tight: for graphs with cop number 1, the cop can always win within $n?4$ rounds. In this paper, we show that the upper bound is tight when $k\ge 2$: for fixed $k\ge 2$, we construct arbitrarily large graphs $G$ having capture time at least ${\left(\frac{\left|V\left(G\right)\right|}{40k^4}\right)}^{k+1}$.In the process of proving our main result, we establish results that may be of independent interest. In particular, we show that the problem of deciding whether $k$ cops can capture a robber on a directed graph is polynomial-time equivalent to deciding whether $k$ cops can capture a robber on an undirected graph. As a corollary of this fact, we obtain a relatively short proof of a major conjecture of Goldstein and Reingold (1995), which was recently proved through other means (Kinnersley, 2015). We also show that $n$-vertex strongly-connected directed graphs with cop number 1 can have capture time $\Omega \left(n^2\right)$, thereby showing that the result of Bonato et al. (2009) does not extend to the directed setting.     

On k-symmetries of hyperbolic spaces

We determine all the possible pointwise k-symmetric spaces of negative constant curvature. In general, such spaces are not k-symmetric.In fact we show that, for all $n?3$, $k\ne 2$, $H^n$ is not k-symmetric, i.e., for any set of selected k-symmetries, one for each point of $H^n$, the regularity condition does not hold.     

On mixed Moore graphs

The Moore bound for a directed graph of maximum out-degree d and diameter k is $M_{d,k}=1+d+d^2+\cdots +d^k$. It is known that digraphs of order $M_{d,k}$ (Moore digraphs) do not exist for $d>1$ and $k>1$. Similarly, the Moore bound for an undirected graph of maximum degree d and diameter k is $M_{d,k}^{*}=1+d+d(d-1)+\cdots +d(d-1{)}^{k-1}$. Undirected Moore graphs only exist in a small number of cases. Mixed (or partially directed) Moore graphs generalize both undirected and directed Moore graphs. In this paper, we shall show that all known mixed Moore graphs of diameter $k=2$ are unique and that mixed Moore graphs of diameter $k⩾3$ do not exist.     

The Picard group of the forms of the affine line and of the additive group

We obtain an explicit upper bound on the torsion of the Picard group of the forms of ${\mathbb{A}}_k^1$ and their regular completions. We also obtain a sufficient condition for the Picard group of the forms of ${\mathbb{A}}_k^1$ to be nontrivial and we give examples of nontrivial forms of ${\mathbb{A}}_k^1$ with trivial Picard groups.     

Partitions of natural numbers with the same weighted representation functions

TextFor any given two positive integers $k_1$ and $k_2$, and any set A of nonnegative integers, let $r_{k_1,k_2}(A,n)$ denote the number of solutions of the equation $n=k_1{a}_1+k_2{a}_2$ with $a_1,a_2\in A$. In this paper, we determine all pairs $k_1,k_2$ of positive integers for which there exists a set $A?\mathbb{N}$ such that $r_{k_1,k_2}(A,n)=r_{k_1,k_2}(\mathbb{N}?A,n)$ for all $n?n_0$. We also pose several problems for further research.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=EnezEsJl0OY.     

Ramsey numbers of odd cycles versus larger even wheels

The generalized Ramsey number $R(G_1,G_2)$ is the smallest positive integer $N$ such that any red–blue coloring of the edges of the complete graph $K_N$ either contains a red copy of $G_1$ or a blue copy of $G_2$. Let $C_m$ denote a cycle of length $m$ and $W_n$ denote a wheel with $n+1$ vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers $R(C_{2k+1},W_n)$ of odd cycles versus larger wheels, leaving open the particular case where $n=2j$ is even and $k<j<3k∕2$. They conjectured that for these values of $j$ and $k$, $R(C_{2k+1},W_{2j})=4j+1$. In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that $R(C_{2k+1},W_{2j})\le 4j+334$. In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that $R(C_{2k+1},W_{2j})=4j+1$ if $j?k\ge 251$, $k<j<3k∕2$, and $j\ge 212299$.     

A new forbidden pair for 6-contractible edges

An edge of a $k$-connected graph is said to be $k$-contractible if the contraction of the edge results in a $k$-connected graph. If every $k$-connected graph with no $k$-contractible edge has either $H_1$ or $H_2$ as a subgraph, then an unordered pair of graphs $\{H_1,H_2\}$ is said to be a forbidden pair for $k$-contractible edges. We prove that $\{K_1+3K_2,K_1+(P_3\cup K_2)\}$ is a forbidden pair for 6-contractible edges, which is an extension of a previous result due to Ando and Kawarabayashi.     

Sparse graphs of girth at least five are packable

A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph $G$ with girth at least $5$ is packable.The conjecture was proved by Faudree et al. with the additional condition that $G$ has at most $\frac{6}{5}n?2$ edges. In this paper, for each integer $k\ge 3$, we prove that every non-star graph with girth at least $5$ and at most $\frac{2k?1}{k}n?{\alpha }_k\left(n\right)$ edges is packable, where ${\alpha }_k\left(n\right)$ is $o\left(n\right)$ for every $k$. This implies that the conjecture is true for sufficiently large planar graphs.     

A sufficient condition for DP-4-colorability

DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-choosable. Furthermore, Jin et al. (2016) showed that for each $k\in \{3,4,5,6\}$, every signed planar graph without $C_k$ is signed 4-choosable. In this paper, we show that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-DP-colorable, which is an extension of the above results.     

On vertex-disjoint cycles and degree sum conditions

This paper considers a degree sum condition sufficient to imply the existence of $k$ vertex-disjoint cycles in a graph $G$. For an integer $t\ge 1$, let ${\sigma }_t\left(G\right)$ be the smallest sum of degrees of $t$ independent vertices of $G$. We prove that if $G$ has order at least $7k+1$ and ${\sigma }_4\left(G\right)\ge 8k?3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint cycles. We also show that the degree sum condition on ${\sigma }_4\left(G\right)$ is sharp and conjecture a degree sum condition on ${\sigma }_t\left(G\right)$ sufficient to imply $G$ contains $k$ vertex-disjoint cycles for $k\ge 2$.