Deletion–contraction to form a polymatroid

Let $M$ be a matroid with rank function $r$, and let $e\in E\left(M\right)$. The deletion–contraction polymatroid with rank function $f=r_{M?e}+r_{M/e}$ will be denoted $P_e\left(M\right)$. Notice that $P_e\left(M\right)$ is uniquely determined by $M$ and $e$. Similarly, a deletion–contraction polymatroid determines $M$, unless $e$ is a loop or co-loop. This paper will characterize all polymatroids of this deletion–contraction form by giving the set of excluded minors. Vertigan conjectured that the class of $GF\left(q\right)$-representable deletion–contraction polymatroids is well-quasi-ordered. From this attractive conjecture, both Rota’s Conjecture and the WQO Conjecture for $GF\left(q\right)$-representable matroids would follow.     

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.     

Primeness property for graded central polynomials of verbally prime algebras

Let F be an infinite field. The primeness property for central polynomials of $M_n(F)$ was established by A. Regev, i.e., if the product of two polynomials in distinct variables is central then each factor is also central. In this paper we consider the analogous property for $M_n(F)$ and determine, within the elementary gradings with commutative neutral component, the ones that satisfy this property, namely the crossed product gradings. Next we consider $M_n(R)$, where R admits a regular grading, with a grading such that $M_n(F)$ is a homogeneous subalgebra and provide sufficient conditions – satisfied by $M_n(E)$ with the trivial grading – to prove that $M_n(R)$ has the primeness property if $M_n(F)$ does. We also prove that the algebras $M_{a,b}(E)$ satisfy this property for ordinary central polynomials. Hence we conclude that, over a field of characteristic zero, every verbally prime algebra has the primeness property.     

Proximity thresholds for matching extension in the torus and Klein bottle

A graph $G$ is said to have the property $E_d(m,n)$ if, given any two disjoint matchings $M$ and $N$ such that the edges within $M$ are pair-wise distance at least $d$ from each other as are the edges in $N$, there is a perfect matching $F$ in $G$ such that $M?F$ and $F\cap N=0?$. This property has been previously studied for planar triangulations as well as projective planar triangulations. Here this study is extended to triangulations of the torus and Klein bottle.     

Quotients of the deformation of Veronesean dual hyperoval in PG(3d,2)

Let $d\ge 3$. In $PG(d(d+3)/2,2)$, there are four known non-isomorphic $d$-dimensional dual hyperovals by now. These are Huybrechts’ dual hyperoval by Huybrechts (2002) [4], Buratti-Del Fra’s dual hyperoval by Buratti and Del Fra (2003) [1], Del Fra and Yoshiara (2005) [3], Veronesean dual hyperoval by Thas and van Maldeghem (2004) [9], Yoshiara (2004) [12] and the dual hyperoval, which is a deformation of Veronesean dual hyperoval by Taniguchi (2009) [6].In this paper, using a generator $\sigma$ of the Galois group $Gal(GF\left(2^{dm}\right)/GF\left(2\right))$ for some $m\ge 3$, we construct a $d$-dimensional dual hyperoval $T_{\sigma }$ in $PG(3d,2)$, which is a quotient of the dual hyperoval of [6]. Moreover, for generators $\sigma ,\tau \in Gal(GF\left(2^{dm}\right)/GF\left(2\right))$, if $T_{\sigma }$ and $T_{\tau }$ are isomorphic, then we show that $\sigma =\tau$ or $\sigma ={\tau }^{?1}$ on $GF\left(2^d\right)$. Hence, we see that there are many non-isomorphic quotients in $PG(3d,2)$ for the dual hyperoval of [6] if $d$ is large.     

Degree-equipartite graphs

A graph $G$ of order $2n$ is called degree-equipartite if for every $n$-element set $A?V\left(G\right)$, the degree sequences of the induced subgraphs $G\left[A\right]$ and $G[V\left(G\right)?A]$ are the same. In this paper, we characterize all degree-equipartite graphs. This answers Problem 1 in the paper by Grünbaum et al. [B. Grünbaum, T. Kaiser, D. Král, and M. Rosenfeld, Equipartite graphs, Israel J. Math. 168 (2008) 431–444].     

A degree condition for a graph to have (a,b)-parity factors

Let $a$ and $b$ be two positive integers such that $a\le b$ and $a\equiv b(mod2)$. A graph $F$ is an $(a,b)$-parity factor of a graph $G$ if $F$ is a spanning subgraph of $G$ and for all vertices $v\in V\left(F\right)$, $d_F\left(v\right)\equiv b(mod2)$ and $a\le d_F\left(v\right)\le b$. In this paper we prove that every connected graph $G$ with $n\ge b(a+b)(a+b+2)∕\left(2a\right)$ vertices has an $(a,b)$-parity factor if $na$ is even, $\delta \left(G\right)\ge (b?a)∕a+a$, and for any two nonadjacent vertices $u,v\in V\left(G\right)$, $max\{d_G\left(u\right),d_G\left(v\right)\}\ge \frac{an}{a+b}$. This extends an earlier result of Nishimura (1992) and strengthens a result of Cai and Li (1998).