Recolouring reflexive digraphs

Given digraphs $G$ and $H$, the colouring graph $\mathbf{Col}(G,H)$ has as its vertices all homomorphism of $G$ to $H$. There is an arc $?\to {?}^{\prime }$ between two homomorphisms if they differ on exactly one vertex $v$, and if $v$ has a loop we also require $?\left(v\right)\to {?}^{\prime }\left(v\right)$. The recolouring problem asks if there is a path in $\mathbf{Col}(G,H)$ between given homomorphisms $?$ and $\psi$. We examine this problem in the case where $G$ is a digraph and $H$ is a reflexive, digraph cycle.We show that for a reflexive digraph cycle $H$ and a reflexive digraph $G$, the problem of determining whether there is a path between two maps in $\mathbf{Col}(G,H)$ can be solved in time polynomial in $G$. When $G$ is not reflexive, we show the same except for certain digraph 4-cycles $H$.     

On super 2-restricted and 3-restricted edge-connected vertex transitive graphs

Let $G=(V\left(G\right),E\left(G\right))$ be a simple connected graph and $F?E\left(G\right)$. An edge set $F$ is an $m$-restricted edge cut if $G?F$ is disconnected and each component of $G?F$ contains at least $m$ vertices. Let ${\lambda }^{\left(m\right)}\left(G\right)$ be the minimum size of all $m$-restricted edge cuts and ${\xi }_m\left(G\right)=min\{\left|\omega \left(U\right)\right|:\left|U\right|=m\text{ and }G\left[U\right]\text{ is connected}\}$, where $\omega \left(U\right)$ is the set of edges with exactly one end vertex in $U$ and $G\left[U\right]$ is the subgraph of $G$ induced by $U$. A graph $G$ is optimal-${\lambda }^{\left(m\right)}$ if ${\lambda }^{\left(m\right)}\left(G\right)={\xi }_m\left(G\right)$. An optimal-${\lambda }^{\left(m\right)}$ graph is called super $m$-restricted edge-connected if every minimum $m$-restricted edge cut is $\omega \left(U\right)$ for some vertex set $U$ with $\left|U\right|=m$ and $G\left[U\right]$ being connected. In this note, we give a characterization of super 2-restricted edge-connected vertex transitive graphs and obtain a sharp sufficient condition for an optimal-${\lambda }^{\left(3\right)}$ vertex transitive graph to be super 3-restricted edge-connected. In particular, a complete characterization for an optimal-${\lambda }^{\left(2\right)}$ minimal Cayley graph to be super 2-restricted edge-connected is obtained.     

Spectral radius of strongly connected digraphs

Let $D$ be a digraph with vertex set $V\left(D\right)$ and $A$ be the adjacency matrix of $D$. The largest eigenvalue of $A$, denoted by $\rho \left(D\right)$, is called the spectral radius of the digraph $D$. In this paper, we establish some sharp upper or lower bounds for digraphs with some given graph parameters, such as clique number, girth, and vertex connectivity, and characterize the corresponding extremal graphs. In addition, we give the exact value of the spectral radii of those digraphs.     

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.     

The list L(2,1)-labeling of planar graphs

Let $\mathbf{N}$ be the set of all positive integers. A list assignment of a graph $G$ is a function $L:V\left(G\right)?2^{\mathbf{N}}$ that assigns each vertex $v$ a list $L\left(v\right)$ for all $v\in V\left(G\right)$. We say that $G$ is $L$-$(2,1)$-choosable if there exists a function $?$ such that $?\left(v\right)\in L\left(v\right)$ for all $v\in V\left(G\right)$, $|?\left(u\right)??\left(v\right)|\ge 2$ if $u$ and $v$ are adjacent, and $|?\left(u\right)??\left(v\right)|\ge 1$ if $u$ and $v$ are at distance 2. The list-$L(2,1)$-labeling number ${\lambda }_l\left(G\right)$ of $G$ is the minimum $k$ such that for every list assignment $L=\{L\left(v\right):|L\left(v\right)|=k,v\in V\left(G\right)\}$, $G$ is $L$-$(2,1)$-choosable. We prove that if $G$ is a planar graph with girth $g\ge 8$ and its maximum degree $\Delta$ is large enough, then ${\lambda }_l\left(G\right)\le \Delta +3$. There are graphs with large enough $\Delta$ and $g\ge 8$ having ${\lambda }_l\left(G\right)=\Delta +3$.     

Choosability with union separation

List coloring generalizes graph coloring by requiring the color of a vertex to be selected from a list of colors specific to that vertex. One refinement of list coloring, called choosability with separation, requires that the intersection of adjacent lists is sufficiently small. We introduce a new refinement, called choosability with union separation, where we require that the union of adjacent lists is sufficiently large. For $t\ge k$, a $(k,t)$-list assignment is a list assignment $L$ where $\left|L\left(v\right)\right|\ge k$ for all vertices $v$ and $|L\left(u\right)\cup L\left(v\right)|\ge t$ for all edges $uv$. A graph is $(k,t)$-choosable if there is a proper coloring for every $(k,t)$-list assignment. We explore this concept through examples of graphs that are not $(k,t)$-choosable, demonstrating sparsity conditions that imply a graph is $(k,t)$-choosable, and proving that all planar graphs are $(3,11)$-choosable and $(4,9)$-choosable.     

On the existence of 3- and 4-kernels in digraphs

Let $D=(V\left(D\right),A\left(D\right))$ be a digraph. A subset $S?V\left(D\right)$ is $k$-independent if the distance between every pair of vertices of $S$ is at least $k$, and it is $?$-absorbent if for every vertex $u$ in $V\left(D\right)?S$ there exists $v\in S$ such that the distance from $u$ to $v$ is less than or equal to $?$. A $k$-kernel is a $k$-independent and $(k?1)$-absorbent set. A kernel is simply a $2$-kernel.A classical result due to Duchet states that if every directed cycle in a digraph $D$ has at least one symmetric arc, then $D$ has a kernel. We propose a conjecture generalizing this result for $k$-kernels and prove it true for $k=3$ and $k=4$.     

Unimodality of independence polynomials of the incidence product of graphs

Given two graphs $G$ and $H$, assume that $V\left(G\right)=\{v_1,v_2,\dots ,v_n\}$ and $U$ is a subset of $V\left(H\right)$. We introduce a new graph operation called the incidence product, denoted by $G\odot H^U$, as follows: insert a new vertex into each edge of $G$, then join with edges those pairs of new vertices on adjacent edges of $G$. Finally, for every vertex $v_i\in V\left(G\right)$, replace it by a copy of the graph $H$ and join every new vertex being adjacent to $v_i$ to every vertex of $U$. It generalizes the line graph operation. We prove that the independence polynomial

$I\left(G\odot H^U;x\right)=I^n(H;x)M\left(G;\frac{x{I}^2(H?U;x)}{I^2(H;x)}\right),$

where $M(G;x)$ is its matching polynomial. Based on this formula, we show that the incidence product of some graphs preserves symmetry, unimodality, reality of zeros of independence polynomials. As applications, we obtain some graphs so-formed having symmetric and unimodal independence polynomials. In particular, the graph $Q\left(G\right)$ introduced by Cvetkovi?, Doob and Sachs has a symmetric and unimodal independence polynomial.     

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.