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.     

Reconfiguration graphs of shortest paths

For a graph $G$ and$a,b\in V\left(G\right)$, the shortest path reconfiguration graph of $G$ with respect to $a$ and$b$ is denoted by $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths between $a$ and$b$ in $G$. Two vertices in $V\left(S(G,a,b)\right)$ are adjacent, if their corresponding paths in $G$ differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

Toughness condition for the existence of all fractional (a,b,k)-critical graphs

In this article, we obtain a sufficient condition related to toughness $\tau \left(G\right)$ for a graph to be all fractional $(a,b,k)$-critical. We prove that if $\tau \left(G\right)\ge \frac{(b^2?1)+ak}{a}$ for some nonnegative integers $a,b,k$, then $G$ is all fractional $(a,b,k)$-critical. Our result improves the known results in Liu and Zhang (2008) and Liu and Cai (2009).     

Vertex-disjoint rainbow triangles in edge-colored graphs

Let $G$ be an edge-colored graph of order $n$. The minimum color degree of $G$, denoted by ${\delta }^c\left(G\right)$, is the largest integer $k$ such that for every vertex $v$, there are at least $k$ distinct colors on edges incident to $v$. We say that an edge-colored graph is rainbow if all its edges have different colors. In this paper, we consider vertex-disjoint rainbow triangles in edge-colored graphs. Li (2013) showed that if ${\delta }^c\left(G\right)\ge (n+1)∕2$, then $G$ contains a rainbow triangle and the lower bound is tight. Motivated by this result, we prove that if $n\ge 20$ and ${\delta }^c\left(G\right)\ge (n+2)∕2$, then $G$ contains two vertex-disjoint rainbow triangles. In particular, we conjecture that if ${\delta }^c\left(G\right)\ge (n+k)∕2$, then $G$ contains $k$ vertex-disjoint rainbow triangles. For any integer $k\ge 2$, we show that if $n\ge 16k-12$ and ${\delta }^c\left(G\right)\ge n∕2+k-1$, then $G$ contains $k$ vertex-disjoint rainbow triangles. Moreover, we provide sufficient conditions for the existence of $k$ edge-disjoint rainbow triangles.     

On the (3,1)-choosability of planar graphs without adjacent cycles of length 5,6,7

A $(k,d)$-list assignment $L$ of a graph $G$ is a mapping that assigns to each vertex $v$ a list $L\left(v\right)$ of at least $k$ colors satisfying $|L\left(x\right)\cap L\left(y\right)|\le d$ for each edge $xy$. A graph $G$ is $(k,d)$-choosable if there exists an $L$-coloring of $G$ for every $(k,d)$-list assignment $L$. This concept is also known as choosability with separation. In this paper, we prove that any planar graph $G$ is $(3,1)$-choosable if any $i$-cycle is not adjacent to a $j$-cycle, where $5\le i\le 6$ and $5\le j\le 7$.     

Flow number and circular flow number of signed cubic graphs

Let $\mathrm{\Phi }(G,\sigma )$ and ${\mathrm{\Phi }}_c(G,\sigma )$ denote the flow number and the circular flow number of a flow-admissible signed graph $(G,\sigma )$, respectively. It is known that $\mathrm{\Phi }(G)=?{\mathrm{\Phi }}_c(G)?$ for every unsigned graph G. Based on this fact, in 2011 Raspaud and Zhu conjectured that $\mathrm{\Phi }(G,\sigma )?{\mathrm{\Phi }}_c(G,\sigma )<1$ holds also for every flow-admissible signed graph $(G,\sigma )$. This conjecture was disproved by Schubert and Steffen using graphs with bridges and vertices of large degree. In this paper we focus on cubic graphs, since they play a crucial role in many open problems in graph theory. For cubic graphs we show that $\mathrm{\Phi }(G,\sigma )=3$ if and only if ${\mathrm{\Phi }}_c(G,\sigma )=3$ and if $\mathrm{\Phi }(G,\sigma )\in \{4,5\}$, then $4\le {\mathrm{\Phi }}_c(G,\sigma )\le \mathrm{\Phi }(G,\sigma )$. We also prove that all pairs of flow number and circular flow number that fulfil these conditions can be achieved in the family of bridgeless cubic graphs and thereby disprove the conjecture of Raspaud and Zhu even for bridgeless signed cubic graphs. Finally, we prove that all currently known flow-admissible graphs without nowhere-zero 5-flow have flow number and circular flow number 6 and propose several conjectures in this area.     

Connected k-dominating graphs

For a graph $G=(V,E)$, the $k$-dominating graph $D_k\left(G\right)$ of $G$ has vertices corresponding to the dominating sets of $G$ having cardinality at most $k$, where two vertices of $D_k\left(G\right)$ are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote the domination and upper domination numbers of $G$ by $\gamma \left(G\right)$ and $\Gamma \left(G\right)$, respectively, and the smallest integer $\epsilon$ for which $D_k\left(G\right)$ is connected for all $k\ge \epsilon$ by $d_0\left(G\right)$. It is known that $\Gamma \left(G\right)+1\le d_0\left(G\right)\le \left|V\right|$, but constructing a graph $G$ such that $d_0\left(G\right)>\Gamma \left(G\right)+1$ appears to be difficult.We present two related constructions. The first construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $G_{k,r}$ such that $\Gamma \left(G_{k,r}\right)=k$, $\gamma \left(G_{k,r}\right)=r+1$ and $d_0\left(G_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)?1$. The second construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $Q_{k,r}$ such that $\Gamma \left(Q_{k,r}\right)=k$, $\gamma \left(Q_{k,r}\right)=r$ and $d_0\left(Q_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)$.     

On incidence choosability of cubic graphs

An incidence of a graph $G$ is a pair $(u,e)$ where $u$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $u$. Two incidences $(u,e)$ and $(v,f)$ of $G$ are adjacent whenever (i) $u=v$, or (ii) $e=f$, or (iii) $uv=e$ or $uv=f$. An incidence$k$-coloring of $G$ is a mapping from the set of incidences of $G$ to a set of $k$ colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a $(2,3)$-bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3.     

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 note on Hadwiger’s conjecture for W5-free graphs with independence number two

The Hadwiger number of a graph $G$, denoted $h\left(G\right)$, is the largest integer $t$ such that $G$ contains $K_t$ as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph $G$, $h\left(G\right)\ge \chi \left(G\right)$, where $\chi \left(G\right)$ denotes the chromatic number of $G$. Let $\alpha \left(G\right)$ denote the independence number of $G$. A graph is $H$-free if it does not contain the graph $H$ as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that $h\left(G\right)\ge \chi \left(G\right)$ for all $H$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $H$ is any graph on four vertices with $\alpha \left(H\right)\le 2$, $H=C_5$, or $H$ is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs $H$ on five vertices with $\alpha \left(H\right)\le 2$. In this note, we prove that $h\left(G\right)\ge \chi \left(G\right)$ for all $W_5$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $W_5$ denotes the wheel on six vertices.     

Strong edge-coloring for planar graphs with large girth

A strong edge-coloring of a graph $G=(V,E)$ is a partition of its edge set $E$ into induced matchings. Let $G$ be a connected planar graph with girth $k\ge 26$ and maximum degree $\Delta$. We show that either $G$ is isomorphic to a subgraph of a very special $\Delta$-regular graph with girth $k$, or $G$ has a strong edge-coloring using at most $2\Delta +\lceil \frac{12(\Delta -2)}{k}\rceil$ colors.