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.     

Induced saturation of P6

A graph $G$ is called $H$-induced-saturated if $G$ does not contain an induced copy of $H$, but removing any edge from $G$ creates an induced copy of $H$ and adding any edge of $G^c$ to $G$ creates an induced copy of $H$. Martin and Smith studied a related problem, and proved that there does not exist a $P_4$-induced-saturated graph, where $P_4$ is the path on 4 vertices. Axenovich and Csikós gave examples of families of graphs $H$ for which $H$-induced-saturated graph $G$ exists, and asked if there exists a $P_n$-induced-saturated graph when $n\ge 5$. Our aim in this short note is to show that there exists a $P_6$-induced-saturated graph.     

Spectra of strongly Deza graphs

A Deza graph G with parameters $(n,k,b,a)$ is a k-regular graph with n vertices such that any two distinct vertices have b or a common neighbours. The children $G_A$ and $G_B$ of a Deza graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in $G_A$ or $G_B$ if and only if they have a or b common neighbours, respectively. A strongly Deza graph is a Deza graph with strongly regular children. In this paper we give a spectral characterisation of strongly Deza graphs, show relationships between eigenvalues, and study strongly Deza graphs which are distance-regular.     

Induced saturation of graphs

A graph $G$ is $H$-saturated for a graph $H$, if $G$ does not contain a copy of $H$ but adding any new edge to $G$ results in such a copy. An $H$-saturated graph on a given number of vertices always exists and the properties of such graphs, for example their highest density, have been studied intensively.A graph $G$ is $H$-induced-saturated if $G$ does not have an induced subgraph isomorphic to $H$, but adding an edge to $G$ from its complement or deleting an edge from $G$ results in an induced copy of $H$. It is not immediate anymore that $H$-induced-saturated graphs exist. In fact, Martin and Smith (2012) showed that there is no $P_4$-induced-saturated graph. Behrens et al. (2016) proved that if $H$ belongs to a few simple classes of graphs such as a class of odd cycles of length at least 5, stars of size at least 2, or matchings of size at least 2, then there is an $H$-induced-saturated graph.This paper addresses the existence question for $H$-induced-saturated graphs. It is shown that Cartesian products of cliques are $H$-induced-saturated graphs for $H$ in several infinite families, including large families of trees. A complete characterization of all connected graphs $H$ for which a Cartesian product of two cliques is an $H$-induced-saturated graph is given. Finally, several results on induced saturation for prime graphs and families of graphs are provided.     

On the unimodality of average edge cover polynomials

The edge cover polynomial of a graph G is the function $E(G,x)={\sum }_{i\ge 1}e(G,i)x^i$, where $e(G,i)$ is the number of edge coverings of G with size i. In this paper, we show that the average edge cover polynomial of order n is reduced to the edge cover polynomial of complete graph $K_n$, based on which we establish that the average edge cover polynomial of order n is unimodal and has at least $n?3$ non-real roots.     

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.     

Endomorphisms and cores of quadratic forms graphs in odd characteristic

A graph G is called a pseudo-core if every endomorphism of G is either an automorphism or a colouring. A graph G is a core if every endomorphism of G is an automorphism. Let ${\mathbb{F}}_q$ be the finite field with q elements where q is a power of an odd prime number. The quadratic forms graph, denoted by $\mathrm{Quad}(n,q)$ where $n\ge 2$, has all quadratic forms on ${\mathbb{F}}_q^n$ as vertices and two vertices f and g are adjacent whenever $\mathrm{rk}(f-g)=1$ or 2. We prove that every $\mathrm{Quad}(n,q)$ is a pseudo-core. Further, when n is even, $\mathrm{Quad}(n,q)$ is a core. When n is odd, $\mathrm{Quad}(n,q)$ is not a core. On the other hand, we completely determine the independence number of $\mathrm{Quad}(n,q)$.     

A local condition for k-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. For a graph $G$ and a vertex $x$ of $G$, let $G\left[N_G\left(x\right)\right]$ be the subgraph induced by the neighborhood of $x$. We prove that if $G\left[N_G\left(x\right)\right]$ has less than $?\frac{k}{2}?$ edges for any vertex $x$ of a $k$-connected graph $G$, then $G$ has a $k$-contractible edge. We also show that the bound $?\frac{k}{2}?$ is sharp.     

On e-cuspidal pairs of finite groups of exceptional Lie type

Let G be a simple, simply connected algebraic group of exceptional type defined over ${\mathbb{F}}_q$ with Frobenius endomorphism $F:G\to G$. Let $??q$ be a good prime for G. We determine the number of irreducible Brauer characters in the quasi-isolated ?-blocks of $G^F$. This is done by proving that generalized e-Harish-Chandra theory holds for the Lusztig series associated to quasi-isolated elements of $G^{?F}$.     

Decomposition of cubic graphs with cyclic connectivity 5

Let G be a cyclically 5-connected cubic graph with a 5-edge-cut separating G into two cyclic components $G_1$ and $G_2$. We prove that each component $G_i$ can be completed to a cyclically 5-connected cubic graph by adding three vertices, unless $G_i$ is a cycle of length five. Our work extends similar results by Andersen et al. for cyclic connectivity 4 from 1988.     

Planar graphs without mutually adjacent 3-, 5-, and 6-cycles are 3-degenerate

A graph G is k-degenerate if every subgraph of G has a vertex with degree at most k. Using the Euler's formula, one can obtain that planar graphs without 3-cycles are 3-degenerate. Wang and Lih, and Fijav? et al. proved the analogue results for planar graphs without 5-cycles and planar graphs without 6-cycles, respectively. Recently, Liu et al. showed that planar graphs without 3-cycles adjacent to 5-cycles are 3-degenerate. In this work, we generalized all aforementioned results by showing that planar graphs without mutually adjacent 3-,5-, and 6-cycles are 3-degenerate. A graph G without mutually adjacent 3-,5-, and 6-cycles means that G cannot contain three graphs, say $G_1,G_2$, and $G_3$, where $G_1$ is a 3-cycle, $G_2$ is a 5-cycle, and $G_3$ is a 6-cycle such that each pair of $G_1,G_2$, and $G_3$ are adjacent. As an immediate consequence, we have that every planar graph without mutually adjacent 3-,5-, and 6-cycles is DP-4-colorable. This consequence also generalizes the result by Chen et al that planar graphs without 5-cycles adjacent to 6-cycles are DP-4-colorable.