Strengthening the Murty–Simon conjecture on diameter 2 critical graphs

A graph is diameter-2-critical if its diameter is 2 but the removal of any edge increases the diameter. A well-studied conjecture, known as the Murty–Simon conjecture, states that any diameter-2-critical graph of order $n$ has at most $?n^2∕4?$ edges, with equality if and only if $G$ is a balanced complete bipartite graph. Many partial results about this conjecture have been obtained, in particular it is known to hold for all sufficiently large graphs, for all triangle-free graphs, and for all graphs with a dominating edge. In this paper, we discuss ways in which this conjecture can be strengthened. Extending previous conjectures in this direction, we conjecture that, when we exclude the class of complete bipartite graphs and one particular graph, the maximum number of edges of a diameter-2-critical graph is at most $?{(n?1)}^2∕4?+1$. The family of extremal examples is conjectured to consist of certain twin-expansions of the 5-cycle (with the exception of a set of thirteen special small graphs). Our main result is a step towards our conjecture: we show that the Murty–Simon bound is not tight for non-bipartite diameter-2-critical graphs that have a dominating edge, as they have at most $?n^2∕4??2$ edges. Along the way, we give a shorter proof of the Murty–Simon conjecture for this class of graphs, and stronger bounds for more specific cases. We also characterize diameter-2-critical graphs of order $n$ with maximum degree $n?2$: they form an interesting family of graphs with a dominating edge and $2n?4$ edges.     

On cycles in regular 3-partite tournaments

A $c$-partite tournament is an orientation of a complete $c$-partite graph. In 2006, Volkmann conjectured that every arc of a regular 3-partite tournament $D$ is contained in an $m$-, $(m+1)$- or $(m+2)$-cycle for each $m\in \{3,4,\dots ,\left|V\left(D\right)\right|?2\}$, and this conjecture was proved to be correct for $3\le m\le 7$. In 2012, Xu et al. conjectured that every arc of an $r$-regular 3-partite tournament $D$ with $r\ge 2$ is contained in a $(3k?1)$- or $3k$-cycle for $k=2,3,\dots ,r$. They proved that this conjecture is true for $k=2$. In this paper, we confirm this conjecture for $k=3$, which also implies that Volkmann’s conjecture is correct for $m=7,8$.     

Minimum supports of functions on the Hamming graphs with spectral constraints

We study functions defined on the vertices of the Hamming graphs $H(n,q)$. The adjacency matrix of $H(n,q)$ has $n+1$ distinct eigenvalues $n(q-1)-q\cdot i$ with corresponding eigenspaces $U_i(n,q)$ for $0\le i\le n$. In this work, we consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum $U_i(n,q)\oplus U_{i+1}(n,q)\oplus \cdots \oplus U_j(n,q)$ for $0\le i\le j\le n$. For the case $i+j\le n$ and $q\ge 3$ we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case $i+j>n$ and $q\ge 4$ we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for $i=j$, $i>\frac{n}{2}$ and $q\ge 5$. In particular, we characterize eigenfunctions from the eigenspace $U_i(n,q)$ with the minimum cardinality of the support for cases $i\le \frac{n}{2}$, $q\ge 3$ and $i>\frac{n}{2}$, $q\ge 5$.     

On the smallest non-trivial tight sets in Hermitian polar spaces H(d,q2), d even

We show that every $x$-tight set of a Hermitian polar spaces $\mathrm{H}(2n,q^2)$, $n\ge 2$, is the union of $x$ disjoint generators of the polar space provided that $x\le \frac{1}{2}(q+1)$. This was known before only when $n\in \{2,3\}$. This result is a contribution to the conjecture that the smallest $x$-tight set of $H(2n,q^2)$ that is not a union of disjoint generators occurs for $x=q+1$ and is for sufficiently large $q$ an embedded subgeometry.     

Sharp upper bounds of the spectral radius of a graph

Let $G$ be a simple connected graph with $n$ vertices and $m$ edges. The spectral radius $\rho \left(G\right)$ of $G$ is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of $\rho \left(G\right)$ which improves some known bounds: If $\frac{(k?2)(k?3)}{2}\le m?n\le \frac{k(k?3)}{2}$, where $k(3\le k\le n)$ is an integer, then $\rho \left(G\right)\le \sqrt{2m?n?k+\frac{5}{2}+\sqrt{2m?2n+\frac{9}{4}}}.$The equality holds if and only if $G$ is a complete graph $K_n$ or $K_4?e$, where $K_4?e$ is the graph obtained from $K_4$ by deleting some edge $e$.     

A simple bijection for enhanced,classical, and 2-distant k-noncrossing partitions

In this note, we give a simple extension map from partitions of subsets of $\left[n\right]$ to partitions of $[n+1]$, which sends $\delta$-distant $k$-crossings to $(\delta +1)$-distant $k$-crossings (and similarly for nestings). This map provides a combinatorial proof of the fact that the numbers of enhanced, classical, and 2-distant $k$-noncrossing partitions are each related to the next via the binomial transform. Our work resolves a recent conjecture of Zhicong Lin and generalizes earlier reduction identities for partitions.     

On the full Brouwer's Laplacian spectrum conjecture

Let G be a simple connected graph and let $S_k(G)$ be the sum of the first k largest Laplacian eigenvalues of G. It was conjectured by Brouwer in 2006 that $S_k(G)\le e(G)+\left(\begin{array}{c}k+1\\ 2\end{array}\right)$ holds for $1\le k\le n?1$. The case $k=2$ was proved by Haemers, Mohammadian and Tayfeh-Rezaie [Linear Algebra Appl., 2010]. In this paper, we propose the full Brouwer's Laplacian spectrum conjecture and we prove the conjecture holds for $k=2$ which also confirm the conjecture of Guan et al. in 2014.     

The combinatorial properties of the Benoumhani polynomials for the Whitney numbers of Dowling lattices

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials $F_{m,n,1}\left(x\right)$ and $F_{m,n,2}\left(x\right)$. Then, he defined $A_m(n,k)$ and $B_m(n,k)$ to be the polynomials satisfying $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{A}_m(n,k)x^{n?k}{(x+1)}^k$ and $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{B}_m(n,k)x^{n?k}{(x+1)}^k$. In this paper, we give a combinatorial interpretation of the coefficients of $A_{m+1}(n,k)$ and prove a symmetry of the coefficients, i.e., $\left[m^s\right]A_{m+1}(n,k)=\left[m^{n?s}\right]A_{m+1}(n,n?k)$. We give a combinatorial interpretation of $B_{m+1}(n,k)$ and prove that $B_{m+1}(n,n?1)$ is a polynomial in $m$ with non-negative integer coefficients. We also prove that if $n\ge 6$ then all coefficients of $B_{m+1}(n,n?2)$ except the coefficient of $m^{n?1}$ are non-negative integers. For all $n$, the coefficient of $m^{n?1}$ in $B_{m+1}(n,n?2)$ is $?(n?1)$, and when $n\le 5$ some other coefficients of $B_{m+1}(n,n?2)$ are also negative.     

Generating infinitely many satisfactory colorings of positive integers

An $n$-satisfactory coloring of the $n$-smooth integers is an assignment of $n$ colors to the positive integers whose prime factors are at most $n$ so that for each such $m$, the integers $m,2m,\dots ,nm$ receive different colors. In this note, we give a short proof that infinitely many 6-satisfactory colorings of the 6-smooth integers exist and show how the technique of the proof can be applied more generally, including for $n\in \{8,10,12\}$.     

On the asymptotic growth of bipartite graceful permutations

We give exact growth rates for the number of bipartite graceful permutations of the symbols $\{0,1,\dots ,n?1\}$ that start with $a$ for $a\le 14$ (equivalently, $\alpha$-labelings of paths with $n$ vertices that have $a$ as a pendant label). In particular, when $a=14$ the growth is asymptotically like ${\lambda }^n$ for $\lambda \approx 3.461$. The number of graceful permutations of length $n$ grows at least this fast, improving on the best existing asymptotic lower bound of $2.37^n$. Combined with existing theory, this improves the known lower bounds on the number of Hamiltonian decompositions of the complete graph $K_{2n+1}$ and on the number of cyclic oriented triangular embeddings of $K_{12s+3}$ and $K_{12s+7}$. We also give the first exponential lower bound on the number of R-sequencings of ${\mathbb{Z}}_{2n+1}$.     

Remarks on the distribution of colors in Gallai colorings

A Gallai coloring of a complete graph $K_n$ is an edge coloring without triangles colored with three different colors. A sequence $e_1\ge \cdots \ge e_k$ of positive integers is an $(n,k)$-sequence if ${\sum }_{i=1}^k{e}_i=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. An $(n,k)$-sequence is a G-sequence if there is a Gallai coloring of $K_n$ with $k$ colors such that there are $e_i$ edges of color $i$ for all $i,1\le i\le k$. Gyárfás, Pálvölgyi, Patkós and Wales proved that for any integer $k\ge 3$ there exists an integer $g\left(k\right)$ such that every $(n,k)$-sequence is a G-sequence if and only if $n\ge g\left(k\right)$. They showed that $g\left(3\right)=5,g\left(4\right)=8$ and $2k-2\le g\left(k\right)\le 8k^2+1$.We show that $g\left(5\right)=10$ and give almost matching lower and upper bounds for $g\left(k\right)$ by showing that with suitable constants $\alpha ,\beta >0$, $\frac{\alpha k^{1.5}}{lnk}\le g\left(k\right)\le \beta k^{1.5}$ for all sufficiently large $k$.     

A plurality problem with three colors and query size three

The Plurality problem - introduced by Aigner - has many variants. In this article we deal with the following version: suppose we are given n balls, each of them colored by one of three colors. A plurality ball is one such that its color class is strictly larger than any other color class. Questioner asks a triplet (or a k-set in general), and Adversary as an answer gives the partition of the triplet (or the k-set) into color classes. Questioner wants to find a plurality ball as soon as possible or show that there is no such ball, while Adversary wants to postpone this.We denote by $A_p(n,k)$ the largest number of queries needed to ask in the worst case if both play optimally. We provide an almost precise result in the case of even n by proving that for $n\ge 4$ even we have$\frac{3}{4}n?2\le A_p(n,3)\le \frac{3}{4}n?\frac{1}{2},$ and for $n\ge 3$ odd we have$\frac{3}{4}n?O(\log ?n)\le A_p(n,3)\le \frac{3}{4}n?\frac{1}{2}.$We also prove some bounds on the number of queries needed to ask in the case $k\ge 3$.     

Large induced subgraphs with three repeated degrees

For any positive integer k, let $C(k)$ denote the least integer such that any n-vertex graph has an induced subgraph with at least $n?C(k)$ vertices, in which at least $\min ?\{k,n?C(k)\}$ vertices are of the same degree. Caro, Shapira and Yuster initially studied this parameter and showed that $\mathrm{\Omega }(k\log ?k)\le C(k)\le {(8k)}^k$. For the first nontrivial case, the authors proved that $3\le C(3)\le 6$, and the exact value was left as an open problem. In this paper, we first show that $3\le C(3)\le 4$, improving the former result as well as a recent result of Kogan. For special families of graphs, we prove that $C(3)=3$ for $K_5$-free graphs, and $C(3)=1$ for large $C_{2s+1}$-free graphs. In addition, extending a result of Erd?s, Fajtlowicz and Staton, we assert that every $K_r$-free graph is an induced subgraph of a $K_r$-free graph in which no degree occurs more than three times.     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.