Maximal linear groups induced on the Frattini quotient of a p-group

Let $p>3$ be a prime. For each maximal subgroup $H?\mathrm{GL}(d,p)$ with $|H|?p^{3d+1}$, we construct a d-generator finite p-group G with the property that $\mathrm{Aut}(G)$ induces H on the Frattini quotient $G/\mathrm{\Phi }(G)$ and $|G|?p^{\frac{d^4}{2}}$. A significant feature of this construction is that $|G|$ is very small compared to $|H|$, shedding new light upon a celebrated result of Bryant and Kovács. The groups G that we exhibit have exponent p, and of all such groups G with the desired action of H on $G/\mathrm{\Phi }(G)$, the construction yields groups with smallest nilpotency class, and in most cases, the smallest order.     

Essential edge connectivity of line graphs

Let $G$ be a graph and $L\left(G\right)$ be its line graph. In 1969, Chartrand and Stewart proved that ${\kappa }^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }^{\prime }\left(G\right)?2$, where ${\kappa }^{\prime }\left(G\right)$ and ${\kappa }^{\prime }\left(L\left(G\right)\right)$ denote the edge connectivity of $G$ and $L\left(G\right)$ respectively. We show a similar relationship holds for the essential edge connectivity of $G$ and $L\left(G\right)$, written ${\kappa }_e^{\prime }\left(G\right)$ and ${\kappa }_e^{\prime }\left(L\left(G\right)\right)$, respectively. In this note, it is proved that if $L\left(G\right)$ is not a complete graph and $G$ does not have a vertex of degree two, then ${\kappa }_e^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }_e^{\prime }\left(G\right)?2$. An immediate corollary is that $\kappa \left(L^2\left(G\right)\right)\ge 2\kappa \left(L\left(G\right)\right)?2$ for such graphs $G$, where the vertex connectivity of the line graph $L\left(G\right)$ and the second iterated line graph $L^2\left(G\right)$ are written as $\kappa \left(L\left(G\right)\right)$ and $\kappa \left(L^2\left(G\right)\right)$ respectively.     

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 characteristic polynomial and the matchings polynomial of a weighted oriented graph

Let $G^{\sigma }$ be a weighted oriented graph with skew adjacency matrix $S(G^{\sigma })$. Then $G^{\sigma }$ is usually referred as the weighted oriented graph associated to $S(G^{\sigma })$. Denote by $?(G^{\sigma }\text{;}\lambda )$ the characteristic polynomial of the weighted oriented graph $G^{\sigma }$, which is defined as$?(G^{\sigma }\text{;}\lambda )=\mathit{det}(\lambda I_n-S(G^{\sigma }))=\sum _{i=0}^n{a}_i(G^{\sigma }){\lambda }^{n-i}\text{.}$In this paper, we begin by interpreting all the coefficients of the characteristic polynomial of an arbitrary real skew symmetric matrix in terms of its associated oriented weighted graph. Then we establish recurrences for the characteristic polynomial and deduce a formula on the matchings polynomial of an arbitrary weighted graph. In addition, some miscellaneous results concerning the number of perfect matchings and the determinant of the skew adjacency matrix of an unweighted oriented graph are given.     

Problems on matchings and independent sets of a graph

Let $G$ be a finite simple graph. For $X?V\left(G\right)$, the difference of $X$, $d\left(X\right)?\left|X\right|?\left|N\left(X\right)\right|$ where $N\left(X\right)$ is the neighborhood of $X$ and $max\{d\left(X\right):X?V\left(G\right)\}$ is called the critical difference of $G$. $X$ is called a critical set if $d\left(X\right)$ equals the critical difference and $\ker \left(G\right)$ is the intersection of all critical sets. $\mathrm{diadem}\left(G\right)$ is the union of all critical independent sets. An independent set $S$ is an inclusion minimal set with$d\left(S\right)>0$ if no proper subset of $S$ has positive difference.A graph $G$ is called a König–Egerváry graph if the sum of its independence number $\alpha \left(G\right)$ and matching number $\mu \left(G\right)$ equals $\left|V\left(G\right)\right|$.In this paper, we prove a conjecture which states that for any graph the number of inclusion minimal independent set $S$ with $d\left(S\right)>0$ is at least the critical difference of the graph.We also give a new short proof of the inequality $\left|\ker \left(G\right)\right|+\left|\mathrm{diadem}\left(G\right)\right|\le 2\alpha \left(G\right)$.A characterization of unicyclic non-König–Egerváry graphs is also presented and a conjecture which states that for such a graph $G$, the critical difference equals $\alpha \left(G\right)?\mu \left(G\right)$, is proved.We also make an observation about $\ker \left(G\right)$ using Edmonds–Gallai Structure Theorem as a concluding remark.     

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 maximum matchings in König–Egerváry graphs

For a graph $G$ let $\alpha \left(G\right),\mu \left(G\right)$, and $\tau \left(G\right)$ denote its independence number, matching number, and vertex cover number, respectively. If $\alpha \left(G\right)+\mu \left(G\right)=\left|V\left(G\right)\right|$ or, equivalently, $\mu \left(G\right)=\tau \left(G\right)$, then $G$ is a König–Egerváry graph.In this paper we give a new characterization of König–Egerváry graphs.     

Elements related to the largest complete excursion of a reflected BM stopped at a fixed time. Application to local score

We calculate the density function of $(U^1\left(t\right),{\theta }^1\left(t\right))$, where $U^1\left(t\right)$ is the maximum over $[0,g\left(t\right)]$ of a reflected Brownian motion $U$, where $g\left(t\right)$ stands for the last zero of $U$ before $t$, ${\theta }^1\left(t\right)=f^1\left(t\right)-g^1\left(t\right)$, $f^1\left(t\right)$ is the hitting time of the level $U^1\left(t\right)$, and $g^1\left(t\right)$ is the left-hand point of the interval straddling $f^1\left(t\right)$. We also calculate explicitly the marginal density functions of $U^1\left(t\right)$ and ${\theta }^1\left(t\right)$. Let $U_n^1$ and ${\theta }_n^1$ be the analogs of $U^1\left(t\right)$ and ${\theta }^1\left(t\right)$ respectively where the underlying process $\left(U_n\right)$ is the Lindley process, i.e. the difference between a centered real random walk and its minimum. We prove that $(\frac{U_n^1}{\sqrt{n}},\frac{{\theta }_n^1}{n})$ converges weakly to $(U^1\left(1\right),{\theta }^1\left(1\right))$ as $n\to \infty$.     

On prisms,Möbius ladders and the cycle space of dense graphs

For a graph $G$, let $\left|G\right|$ denote its number of vertices, $\delta \left(G\right)$ its minimum degree and $Z_1(G;{\mathbb{F}}_2)$ its cycle space. Call a graph Hamilton-generated if and only if every cycle in $G$ is a symmetric difference of some Hamilton circuits of $G$. The main purpose of this paper is to prove: for every $\gamma >0$ there exists $n_0\in \mathbb{Z}$ such that for every graph $G$ with $\left|G\right|⩾n_0$ vertices,

• (1)if $\delta \left(G\right)⩾(\frac{1}{2}+\gamma )\left|G\right|$ and $\left|G\right|$ is odd, then $G$ is Hamilton-generated,
• (2)if $\delta \left(G\right)⩾(\frac{1}{2}+\gamma )\left|G\right|$ and $\left|G\right|$ is even, then the set of all Hamilton circuits of $G$ generates a codimension-one subspace of $Z_1(G;{\mathbb{F}}_2)$ and the set of all circuits of $G$ having length either $\left|G\right|-1$ or $\left|G\right|$ generates all of $Z_1(G;{\mathbb{F}}_2)$,
• (3)if $\delta \left(G\right)⩾(\frac{1}{4}+\gamma )\left|G\right|$ and $G$ is balanced bipartite, then $G$ is Hamilton-generated.

All these degree-conditions are essentially best-possible. The implications in (1) and (2) give an asymptotic affirmative answer to a special case of an open conjecture which according to [I.B.-A. Hartman, Long cycles generate the cycle space of a graph, European J. Combin. 4 (3) (1983) 237–246] originates with A. Bondy.