Degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number

Let $D$ be a finite and simple digraph with vertex set $V\left(D\right)$. For a vertex $v\in V\left(D\right)$, the degree $d\left(v\right)$ of $v$ is defined as the minimum value of its out-degree $d^{+}\left(v\right)$ and its in-degree $d^{?}\left(v\right)$. If $D$ is a graph or a digraph with minimum degree $\delta$ and edge-connectivity $\lambda$, then $\lambda \le \delta$. A graph or a digraph is maximally edge-connected if $\lambda =\delta$. A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree.In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph.     

Polynomial kernels for deletion to classes of acyclic digraphs

We consider the problem to find a set $X$ of vertices (or arcs) with $\left|X\right|\le k$ in a given digraph $G$ such that $D=G-X$ is an acyclic digraph. In its generality, this is Directed Feedback Vertex Set (or Directed Feedback Arc Set); the existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider the vertex deletion problem with an additional restriction on $D$, namely that $D$ must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of the above three restrictions we can obtain a kernel with $k^{O\left(1\right)}$ vertices on general digraphs. We also show that the arc deletion problem with the first two restrictions (out-forest and out-tree) can be solved in polynomial time; this contrasts the status of the vertex deletion problem of these restrictions, which is $\mathrm{NP}$-hard even for acyclic digraphs. The arc and vertex deletion problem with the third restriction (pumpkin), however, can be solved in polynomial time for acyclic digraphs, but becomes $\mathrm{NP}$-hard for general digraphs. We believe that the idea of restricting $D$ could yield new insights towards resolving the status of Directed Feedback Vertex Set.     

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.     

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$.     

Starlike trees whose maximum degree exceed 4 are determined by their Q-spectra

Let $A(G)$ and $D(G)$ be the adjacency matrix and the degree matrix of a graph $G$, respectively. The matrix $D(G)+A(G)$ is called the signless Laplacian matrix of $G$. The spectrum of the matrix $D(G)+A(G)$ is called the Q-spectrum of $G$. A graph is said to be determined by its Q-spectrum if there is no other non-isomorphic graph with the same Q-spectrum. In this paper, we prove that all starlike trees whose maximum degree exceed $4$ are determined by their Q-spectra.     

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$.     

Decomposition of integer-valued polynomial algebras

Let D be a commutative domain with field of fractions K, let A be a torsion-free D-algebra, and let B be the extension of A to a K-algebra. The set of integer-valued polynomials on A is $\mathrm{Int}(A)=\{f\in B[X]|f(A)?A\}$, and the intersection of $\mathrm{Int}(A)$ with $K[X]$ is ${\mathrm{Int}}_K(A)$, which is a commutative subring of $K[X]$. The set $\mathrm{Int}(A)$ may or may not be a ring, but it always has the structure of a left ${\mathrm{Int}}_K(A)$-module.A D-algebra A which is free as a D-module and of finite rank is called ${\mathrm{Int}}_K$-decomposable if a D-module basis for A is also an ${\mathrm{Int}}_K(A)$-module basis for $\mathrm{Int}(A)$; in other words, if $\mathrm{Int}(A)$ can be generated by ${\mathrm{Int}}_K(A)$ and A. A classification of such algebras has been given when D is a Dedekind domain with finite residue rings. In the present article, we modify the definition of ${\mathrm{Int}}_K$-decomposable so that it can be applied to D-algebras that are not necessarily free by defining A to be ${\mathrm{Int}}_K$-decomposable when $\mathrm{Int}(A)$ is isomorphic to ${\mathrm{Int}}_K(A){?}_{D}A$. We then provide multiple characterizations of such algebras in the case where D is a discrete valuation ring or a Dedekind domain with finite residue rings. In particular, if D is the ring of integers of a number field K, we show that an ${\mathrm{Int}}_K$-decomposable algebra A must be a maximal D-order in a separable K-algebra B, whose simple components have as center the same finite unramified Galois extension F of K and are unramified at each finite place of F. Finally, when both D and A are rings of integers in number fields, we prove that ${\mathrm{Int}}_K$-decomposable algebras correspond to unramified Galois extensions of K.