Graph switching, 2-ranks,and graphical Hadamard matrices

We study the behavior of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil–McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order $4^m$. Starting with graphs from known Hadamard matrices of order 64, we find (by computer) many Godsil–McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters $(63,32,16,16)$, $(64,36,20,20)$, and $(64,28,12,12)$ for almost all feasible 2-ranks. In addition we work out the behavior of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order $4^m$ for which the number of related strongly regular graphs with different 2-ranks is unbounded as a function of $m$. The paper extends results from the article ‘Switched symplectic graphs and their 2-ranks’ by the first and the last author.     

Regular saturated graphs and sum-free sets

In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular $K_3$-saturated graph with n vertices. We extend this result to both $K_4$ and $K_5$ and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all $k\ge 2$, there is a regular $C_{2k+1}$-saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to $C_{2k+1}$-saturated graphs is an interesting problem on its own and we state an open problem in this direction.     

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.     

Construction of symplectic graphs by using 2-dimensional symplectic non-isotropic subspaces over finite fields

In most extant studies, symplectic graphs are defined by 1-dimensional subspaces and their orthogonality. In this paper, the symplectic graph is defined by 2-dimensional non-isotropic subspaces and their intersection. The symplectic graph is shown to be a 4-Deza graph. While the first subconstituent is shown to be a 4-Deza graph when $\nu ⩾3$ and a 3-Deza graph when $\nu =2$, the second subconstituent is not regular, and the third subconstituent is a 4-Deza graph except in the case $\nu =2$, when it is empty.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Forcing clique immersions through chromatic number

Building on recent work of Dvořák and Yepremyan, we show that every simple graph of minimum degree $7t+7$ contains $K_t$ as an immersion and that every graph with chromatic number at least $3.54t+4$ contains $K_t$ as an immersion. We also show that every graph on $n$ vertices with no independent set of size three contains $K_{2\lfloor n∕5\rfloor }$ as an immersion.     

Improved square coloring of planar graphs

Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that $\frac{3}{2}\mathrm{\Delta }+1$ colors are sufficient to square color every planar graph of maximum degree Δ. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that $2\mathrm{\Delta }+7$ colors are sufficient, which improves the best known bounds when $6?\mathrm{\Delta }?31$.     

Hamiltonian cycles in 7-tough (P3 ∪ 2P1)-free graphs

The toughness of a noncomplete graph G is the maximum real number t such that the ratio of $|S|$ to the number of components of $G?S$ is at least t for every cutset S of G. Determining the toughness for a given graph is NP-hard. Chvátal's toughness conjecture, stating that there exists a constant $t_0$ such that every graph with toughness at least $t_0$ is hamiltonian, is still open for general graphs. A graph is called $(P_3\cup 2P_1)$-free if it does not contain any induced subgraph isomorphic to $P_3\cup 2P_1$, the disjoint union of $P_3$ and two isolated vertices. In this paper, we confirm Chvátal's toughness conjecture for $(P_3\cup 2P_1)$-free graphs by showing that every 7-tough $(P_3\cup 2P_1)$-free graph on at least three vertices is hamiltonian.     

Gallai’s path decomposition conjecture for graphs of small maximum degree

Gallai’s path decomposition conjecture states that the edges of any connected graph on $n$ vertices can be decomposed into at most $\frac{n+1}{2}$ paths. We confirm that conjecture for all graphs with maximum degree at most five.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

Hermitian adjacency matrix of the second kind for mixed graphs

This contribution gives an extensive study on spectra of mixed graphs via its Hermitian adjacency matrix of the second kind (N-matrix for short) introduced by Mohar [25]. This matrix is indexed by the vertices of the mixed graph, and the entry corresponding to an arc from u to v is equal to the sixth root of unity $\omega =\frac{1+\mathbf{i}\sqrt{3}}{2}$ (and its symmetric entry is $\overline{\omega }=\frac{1?\mathbf{i}\sqrt{3}}{2}$); the entry corresponding to an undirected edge is equal to 1, and 0 otherwise. The main results of this paper include the following: equivalent conditions for a mixed graph that shares the same spectrum of its N-matrix with its underlying graph are given. A sharp upper bound on the spectral radius is established and the corresponding extremal mixed graphs are identified. Operations which are called two-way and three-way switchings are discussed–they give rise to some cospectral mixed graphs. We extract all the mixed graphs whose rank of its N-matrix is 2 (resp. 3). Furthermore, we show that if $M_G$ is a connected mixed graph with rank 2, then $M_G$ is switching equivalent to each connected mixed graph to which it is cospectral. However, this does not hold for some connected mixed graphs with rank 3. We identify all mixed graphs whose eigenvalues of its N-matrix lie in the range $(?\alpha ,\alpha )$ for $\alpha \in \{\sqrt{2},\sqrt{3},2\}$.     

On 2-walk-regular graphs with a large intersection number c2

For a connected amply regular graph with parameters $(v,k,\lambda ,\mu )$ satisfying $\lambda \le \mu$, it is known that its diameter is bounded by $k$. This was generalized by Terwilliger to $(s,c,a,k)$-graphs satisfying $c\ge max\{a,2\}$. It follows from Terwilliger that a connected amply regular graph with parameters $(v,k,\lambda ,\mu )$ satisfying $\mu >\frac{k}{3}\ge 1$ and $\mu \ge \lambda$ has diameter at most 7.In this paper we will classify the 2-walk-regular graphs with valency $k\ge 3$ and diameter at least 4 such that its intersection number $c_2$ satisfies $c_2>\frac{k}{3}$. This result generalizes a result of Koolen and Park for distance-regular graphs. And we show that if such a 2-walk-regular graph is not distance-regular, then it is the incidence graph of a group divisible design with the dual property with parameters $(2,m;k;0,{\lambda }_2)$.