For any graph $G$, let $V\left(G\right)$ and $E\left(G\right)$ denote the vertex set and the edge set of $G$ respectively. The Boolean function graph $B(G,L(G),\mathrm{N}INC)$ of $G$ is a graph with vertex set $V\left(G\right)\cup E\left(G\right)$ and two vertices in $B(G,L(G),\mathrm{N}INC)$ are adjacent if and only if they correspond to two adjacent vertices of $G$, two adjacent edges of $G$ or to a vertex and an edge not incident to it in $G$. For brevity, this graph is denoted by $B_1\left(G\right)$. In this paper, structural properties of $B_1\left(G\right)$ and its complement including traversability and eccentricity properties are studied. In addition,...

We present some extensions of the Borel-Cantelli Lemma in terms of moments. Our result can be viewed as a new improvement to the Borel-Cantelli Lemma. Our proofs are based on the expansion of moments of some partial sums by using Stirling numbers. We also give a comment concerning the results of Petrov V.V., A generalization of the Borel-Cantelli Lemma, Statist. Probab. Lett. 67 (2004), no. 3, 233–239.

Let ${\mu }_{n-1}\left(G\right)$ be the algebraic connectivity, and let ${\mu }_1\left(G\right)$ be the Laplacian spectral radius of a $k$-connected graph $G$ with $n$ vertices and $m$ edges. In this paper, we prove that $${\mu }_{n-1}\left(G\right)\ge \frac{2n{k}^2}{(n(n-1)-2m)(n+k-2)+2k^2},$$ with equality if and only if $G$ is the complete graph $K_n$ or $K_n-e$. Moreover, if $G$ is non-regular, then $${\mu }_1\left(G\right)<2\Delta -\frac{2(n\Delta -2m)k^2}{2(n\Delta -2m)(n^2-2n+2k)+n{k}^2},$$ where $\Delta$ stands for the maximum degree of $G$. Remark that in some cases, these two inequalities improve some previously known results.

We use an algebraic method to classify the generalized permutation star-graphs, and we use the classification to determine the toughness of all generalized permutation star-graphs.

A $0/1$-simplex is the convex hull of $n+1$ affinely independent vertices of the unit $n$-cube $I^n$. It is nonobtuse if none of its dihedral angles is obtuse, and acute if additionally none of them is right. Acute $0/1$-simplices in $I^n$ can be represented by $0/1$-matrices $P$ of size $n\times n$ whose Gramians $G=P^{\top }P$ have an inverse that is strictly diagonally dominant, with negative off-diagonal entries. In this paper, we will prove that the positive part $D$ of the transposed inverse $P^{-\top }$ of $P$ is doubly stochastic and has the same support...

Homotopic methods are employed for the characterization of the complete digraphs which are the composition of non-trivial highly regular tournaments.