On a lower bound for the connectivity of the independence complex of a graph

Aharoni, Berger and Ziv proposed a function which is a lower bound for the connectivity of the independence complex of a graph. They conjectured that this bound is optimal for every graph. We give two different arguments which show that the conjecture is false.     

A simple proof of an inequality connecting the alternating number of independent sets and the decycling number

If s_k denotes the number of independent sets of cardinality k and α(G) is the size of a maximum independent set in graph G, then I(G;x)=s₀+s₁x+?+s_α(G)x^α(G) is the independence polynomial of G (Gutman and Harary, 1983) [8].In this paper we provide an elementary proof of the inequality|I(G;−1)|≤2^φ(G) (Engström, 2009) [7], where φ(G) is the decycling number of G (Beineke and Vandell, 1997) [3], namely, the minimum number of vertices that have to be deleted in order to turn G into a forest.     

Notes on “A survey of fuzzy implication algebras and their axiomatization”

In this note, we present a correction of Theorem 2 in the paper [1], and show that all the conditions (I1)–(I5) in the definition of fuzzy implication algebras are independent of each other. In addition, we prove that the class of all commutative fuzzy implication algebras forms an equational algebra class.     

Exponential independence

For a set $S$ of vertices of a graph $G$, a vertex $u$ in $V\left(G\right)?S$, and a vertex $v$ in $S$, let ${\mathrm{dist}}_{(G,S)}(u,v)$ be the distance of $u$ and $v$ in the graph $G?(S?\left\{v\right\})$. Dankelmann et al. (2009) define $S$ to be an exponential dominating set of $G$ if $w_{(G,S)}\left(u\right)\ge 1$ for every vertex $u$ in $V\left(G\right)?S$, where $w_{(G,S)}\left(u\right)={\sum }_{v\in S}{\left(\frac{1}{2}\right)}^{{\mathrm{dist}}_{(G,S)}(u,v)?1}$. Inspired by this notion, we define $S$ to be an exponential independent set of $G$ if $w_{(G,S?\left\{u\right\})}\left(u\right)<1$ for every vertex $u$ in $S$, and the exponential independence number ${\alpha }_e\left(G\right)$ of $G$ as the maximum order of an exponential independent set of $G$.Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs $G$ for which ${\alpha }_e\left(H\right)$ equals the independence number $\alpha \left(H\right)$ for every induced subgraph $H$ of $G$, and we give an explicit characterization of all trees $T$ with ${\alpha }_e\left(T\right)=\alpha \left(T\right)$.     

Exploiting independencies to compute semigraphoid and graphoid structures

We deal with conditional independencies, which have a fundamental role in probability and multivariate statistics. The structure of probabilistic independencies is described by semigraphoids or, for strictly positive probabilities, by graphoids. In this paper, given a set of independencies compatible with a probability, the attention is focused toward the problem of computing efficiently the closure with respect to the semigraphoid and graphoid structures. We introduce a suitable notion of projection in order to provide a new method which properly uses conditional independence statements.     

A note on Vizing's independence number conjecture of edge chromatic critical graphs

In 1968, Vizing conjectured that, if G is a Δ-critical graph with n vertices, then α(G)?n/2, where α(G) is the independence number of G. In this note, we verify this conjecture for n?2Δ.     

A test for independence of two stationary infinite order autoregressive processes

This paper considers the independence test for two stationary infinite order autoregressive processes. For a test, we follow the empirical process method and construct the Cramér-von Mises type test statistics based on the least squares residuals. It is shown that the proposed test statistics behave asymptotically the same as those based on true errors. Simulation results are provided for illustration.