Minimal homogeneous Steiner 2-(v,3) trades

A Steiner 2-$(v,3)$ trade is a pair $(T_1,T_2)$ of disjoint partial Steiner triple systems, each on the same set of $v$ points, such that each pair of points occurs in $T_1$ if and only if it occurs in $T_2$. A Steiner 2-$(v,3)$ trade is called d-homogeneous if each point occurs in exactly d blocks of $T_1$ (or $T_2$). In this paper we construct minimal d-homogeneous Steiner 2-$(v,3)$ trades of foundation $v$ and volume $\mathit{dv}/3$ for sufficiently large values of $v$. (Specifically, $v>3(1.75d^2+3)$ if $v$ is divisible by 3 and $v>d(4^{d/3+1}+1)$ otherwise.)     

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$.     

On a conjecture of the Randić index and the minimum degree of graphs

The Randi? index $R\left(G\right)$ of a graph $G$ is defined by $R\left(G\right)={\sum }_{uv}\frac{1}{\sqrt{d\left(u\right)d\left(v\right)}}$, where $d\left(u\right)$ is the degree of a vertex $u$ and the summation extends over all edges $uv$ of $G$. Delorme et al. (2002)  [6] put forward a conjecture concerning the minimum Randi? index among all$n$-vertex connected graphs with the minimum degree at least $k$. In this work, we show that the conjecture is true given the graph contains $k$ vertices of degree $n?1$. Further, it is true among $k$-trees.     

Dense uniform hypergraphs have high list chromatic number

The first author showed that the list chromatic number of every graph with average degree $d$ is at least $(0.5?o\left(1\right)){log}_{2}d$. We prove that for $r\ge 3$, every $r$-uniform hypergraph in which at least half of the $(r?1)$-vertex subsets are contained in at least $d$ edges has list chromatic number at least $\frac{lnd}{100r^3}$. When $r$ is fixed, this is sharp up to a constant factor.     

List 3-dynamic coloring of graphs with small maximum average degree

An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that for any vertex $v$, there are at least $min\{r,{deg}_G\left(v\right)\}$ distinct colors in $N_G\left(v\right)$. The $r$-dynamic chromatic number${\chi }_r^d\left(G\right)$ of a graph $G$ is the least $k$ such that there exists an $r$-dynamic $k$-coloring of $G$. The list$r$-dynamic chromatic number of a graph $G$ is denoted by $c{h}_r^d\left(G\right)$.Recently, Loeb et al. (0000) showed that the list $3$-dynamic chromatic number of a planar graph is at most 10. And Cheng et al. (0000) studied the maximum average condition to have ${\chi }_3^d\left(G\right)\le 4,5$, or $6$. On the other hand, Song et al. (2016) showed that if $G$ is planar with girth at least 6, then ${\chi }_r^d\left(G\right)\le r+5$ for any $r\ge 3$.In this paper, we study list 3-dynamic coloring in terms of maximum average degree. We show that $c{h}_3^d\left(G\right)\le 6$ if $mad\left(G\right)<\frac{18}{7}$, $c{h}_3^d\left(G\right)\le 7$ if $mad\left(G\right)<\frac{14}{5}$, and $c{h}_3^d\left(G\right)\le 8$ if $mad\left(G\right)<3$. All of the bounds are tight.     

Maximum average degree and relaxed coloring

We say a graph is $(d,d,\dots ,d,0,\dots ,0)$-colorable with $a$ of $d$’s and $b$ of $0$’s if $V\left(G\right)$ may be partitioned into $b$ independent sets $O_1,O_2,\dots ,O_b$ and $a$ sets $D_1,D_2,\dots ,D_a$ whose induced graphs have maximum degree at most $d$. The maximum average degree, $mad\left(G\right)$, of a graph $G$ is the maximum average degree over all subgraphs of $G$. In this note, for nonnegative integers $a,b$, we show that if $mad\left(G\right)<\frac{4}{3}a+b$, then $G$ is $(1_1,1_2,\dots ,1_a,0_1,\dots ,0_b)$-colorable.     

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.     

3-Restricted arc connectivity of digraphs

The $k$-restricted arc connectivity of digraphs is a common generalization of the arc connectivity and the restricted arc connectivity. An arc subset $S$ of a strong digraph $D$ is a $k$-restricted arc cut if $D?S$ has a strong component $D^{\prime }$ with order at least $k$ such that $D?V\left(D^{\prime }\right)$ contains a connected subdigraph with order at least $k$. The $k$-restricted arc connectivity ${\lambda }^k\left(D\right)$ of a digraph $D$ is the minimum cardinality over all $k$-restricted arc cuts of $D$.Let $D$ be a strong digraph with order $n\ge 6$ and minimum degree $\delta \left(D\right)$. In this paper, we first show that ${\lambda }^3\left(D\right)$ exists if $\delta \left(D\right)\ge 3$ and, furthermore, ${\lambda }^3\left(D\right)\le {\xi }^3\left(D\right)$ if $\delta \left(D\right)\ge 4$, where ${\xi }^3\left(D\right)$ is the minimum 3-degree of $D$. Next, we prove that ${\lambda }^3\left(D\right)={\xi }^3\left(D\right)$ if $\delta \left(D\right)\ge \frac{n+3}{2}$. Finally, we give examples showing that these results are best possible in some sense.     

Weak version of restriction estimates for spheres and paraboloids in finite fields

We study $L^p-L^r$ restriction estimates for algebraic varieties in d-dimensional vector spaces over finite fields. Unlike the Euclidean case, if the dimension d is even, then it is conjectured that the $L^{(2d+2)/(d+3)}-L^2$ Stein–Tomas restriction result can be improved to the $L^{(2d+4)/(d+4)}-L^2$ estimate for both spheres and paraboloids in finite fields. In this paper we show that the conjectured $L^p-L^2$ restriction estimate holds in the specific case when test functions under consideration are restricted to d-coordinate functions or homogeneous functions of degree zero. To deduce our result, we use the connection between the restriction phenomena for our varieties in d dimensions and those for homogeneous varieties in $(d+1)$ dimensions.     

d-matching in 3-uniform hypergraphs

A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. A $d$-matching in a 3-uniform hypergraph $H$ is a matching of size $d$. Let $V_1,V_2$ be a partition of $n$ vertices such that $\left|V_1\right|=2d?1$ and $\left|V_2\right|=n?2d+1$. Denote by $E_3(2d?1,n?2d+1)$ the 3-uniform hypergraph with vertex set $V_1\cup V_2$ consisting of all those edges which contain at least two vertices of $V_1$. Let $H$ be a 3-uniform hypergraph of order $n\ge 9d^2$ such that $deg\left(u\right)+deg\left(v\right)>2\left[\left(\genfrac{}{}{0ex}{}{n?1}{2}\right)?\left(\genfrac{}{}{0ex}{}{n?d}{2}\right)\right]$ for any two adjacent vertices $u,v\in V\left(H\right)$. In this paper, we prove $H$ contains a $d$-matching if and only if $H$ is not a subgraph of $E_3(2d?1,n?2d+1)$.     

Which cospectral graphs have same degree sequences

Two graphs are said to be $L$-cospectral (respectively, $Q$-cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph $G$ is said to be $L?DS$ (respectively, $Q?DS$) if there does not exist other non-isomorphic graph $H$ such that $H$ and $G$ are $L$-cospectral (respectively, $Q$-cospectral). Let $d_1\left(G\right)\ge d_2\left(G\right)\ge ?\ge d_n\left(G\right)$ be the degree sequence of a graph $G$ with $n$ vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with $d_1\left(G\right)\in \{4,5\}$), if $H$ is $L$-cospectral (respectively, $Q$-cospectral) with a connected graph $G$ and $d_2\left(G\right)=2$, then $H$ has the same degree sequence as $G$. A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both $L?DS$, which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014).     

Nonexistence of some linear codes over the field of order four

We consider the problem of determining $n_4(5,d)$, the smallest possible length $n$ for which an ${[n,5,d]}_4$ code of minimum distance $d$ over the field of order 4 exists. We prove the nonexistence of ${[g_4(5,d)+1,5,d]}_4$ codes for $d=31,47,48,59,60,61,62$ and the nonexistence of a ${[g_4(5,d),5,d]}_4$ code for $d=138$ using the geometric method through projective geometries, where $g_q(k,d)={\sum }_{i=0}^{k?1}?d∕q^i?$. This yields to determine the exact values of $n_4(5,d)$ for these values of $d$. We also give the updated table for $n_4(5,d)$ for all $d$ except some known cases.     

Enumerating cycles in the graph of overlapping permutations

The graph of overlapping permutations is a directed graph that is an analogue to the De Bruijn graph. It consists of vertices that are permutations of length $n$ and edges that are permutations of length $n+1$ in which an edge $a_1?a_{n+1}$ would connect the standardization of $a_1?a_n$ to the standardization of $a_2?a_{n+1}$. We examine properties of this graph to determine where directed cycles can exist, to count the number of directed $2$-cycles within the graph, and to enumerate the vertices that are contained within closed walks and directed cycles of more general lengths.     

3-dynamic coloring of planar triangulations

An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that any vertex $v$ has at least $min\{r,{deg}_G\left(v\right)\}$ distinct colors in $N_G\left(v\right)$. The $r$-dynamic chromatic number${\chi }_r^d\left(G\right)$ of a graph $G$ is the least $k$ such that there exists an $r$-dynamic $k$-coloring of $G$.Loeb et al. (2018) showed that if $G$ is a planar graph, then ${\chi }_3^d\left(G\right)\le 10$, and there is a planar graph $G$ with ${\chi }_3^d\left(G\right)=7$. Thus, finding an optimal upper bound on ${\chi }_3^d\left(G\right)$ for a planar graph $G$ is a natural interesting problem. In this paper, we show that ${\chi }_3^d\left(G\right)\le 5$ if $G$ is a planar triangulation. The upper bound is sharp.