On the imaginary parts of chromatic roots

While much attention has been directed to the maximum modulus and maximum real part of chromatic roots of graphs of order $n$ (ie, with $n$ vertices), relatively little is known about the maximum imaginary part of such graphs. We prove that the maximum imaginary part can grow linearly in the order of the graph. We also show that for any fixed $\text{◂+▸}p\in \left(0,1\right)$, almost every random graph $G$ in the Erdös-Rényi model has a nonreal root.     

On posets and independence spaces

By constructing a correspondence relationship between independence spaces and posets, under isomorphism, this paper characterizes loopless independence spaces and applies this characterization to reformulate certain results on independence spaces in poset frameworks. These state that the idea provided in this paper is a new approach for the study of independence spaces. We outline our future work finally.     

An algorithm for calculating the independence and vertex-cover polynomials of a graph

The independence polynomial, ω(G,x)=∑w_kx^k, of a graph, G, has coefficients, w_k, that enumerate the ways of selecting k vertices from G so that no two selected vertices share an edge. The independence number of G is the largest value of k for which w_k≠0. Little is known of less straightforward relationships between graph structure and the properties of ω(G,x), in part because of the difficulty of calculating values of w_k for specific graphs. This study presents a new algorithm for these calculations which is both faster than existing ones and easily adaptable to high-level computer languages.     

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.     

Log-concavity of some independence polynomials via a partial ordering

Schwenk proved in 1981 that the edge independence polynomial of a graph is unimodal. It has been known since 1987 that the (vertex) independence polynomial of a graph need not be unimodal. Alavi et al. have asked whether the independence polynomial of a tree is unimodal. We apply some results on the log-concavity of combinations of log-concave sequences toward establishing the log-concavity (and, thus, the unimodality) of the independence numbers of some families of trees and related graphs.     

A note on the edge cover number and independence number in hypergraphs

Consider a hypergraph of rank r>2 with m edges, independence number α and edge cover number ρ. We prove the inequality

     

A note about the average number of real roots of a Bernstein polynomial system

We prove that the real roots of normal random homogeneous polynomial systems with n+1$n+1$ variables and given degrees are, in some sense, equidistributed in the projective space P(Rⁿ⁺¹)$\mathbb{P}\left({\mathbb{R}}^{n+1}\right)$. From this fact we compute the average number of real roots of normal random polynomial systems given in the Bernstein basis.     

On trees with real-rooted independence polynomial

The independence polynomial of a graph $G$ is

$I(G,x)=\sum _{k\ge 0}{i}_k\left(G\right)x^k,$

where $i_k\left(G\right)$ denotes the number of independent sets of $G$ of size $k$ (note that $i_0\left(G\right)=1$). In this paper we show a new method to prove real-rootedness of the independence polynomials of certain families of trees.In particular we will give a new proof of the real-rootedness of the independence polynomials of centipedes (Zhu’s theorem), caterpillars (Wang and Zhu’s theorem), and we will prove a conjecture of Galvin and Hilyard about the real-rootedness of the independence polynomial of the so-called Fibonacci trees.     

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 note on iterative roots of PM functions

In this paper we study iterative roots of PM functions, a special class of non-monotone functions. Problem 2 in [W. Zhang, PM functions, their characteristic intervals and iterative roots, Ann. Polon. Math. LXV (1997) 119-128] is solved partly and Theorem 4 in that paper is generalized.     

The independence polynomial of rooted products of graphs

A stable (or independent) set in a graph is a set of pairwise nonadjacent vertices thereof. The stability numberα(G) is the maximum size of stable sets in a graph G. The independence polynomial of G is

     

Two problems on independent sets in graphs

Let i_t(G) denote the number of independent sets of size t in a graph G. Levit and Mandrescu have conjectured that for all bipartite G the sequence (i_t(G))_t≥0 (the independent set sequence of G) is unimodal. We provide evidence for this conjecture by showing that this is true for almost all equibipartite graphs. Specifically, we consider the random equibipartite graph G(n,n,p), and show that for any fixed p∈(0,1] its independent set sequence is almost surely unimodal, and moreover almost surely log-concave except perhaps for a vanishingly small initial segment of the sequence. We obtain similar results for .We also consider the problem of estimating i(G)=∑_t≥0i_t(G) for G in various families. We give a sharp upper bound on the number of independent sets in an n-vertex graph with minimum degree δ, for all fixed δ and sufficiently large n. Specifically, we show that the maximum is achieved uniquely by K_δ,n−δ, the complete bipartite graph with δ vertices in one partition class and n−δ in the other.We also present a weighted generalization: for all fixed x>0 and δ>0, as long as n=n(x,δ) is large enough, if G is a graph on n vertices with minimum degree δ then ∑_t≥0i_t(G)x^t≤∑_t≥0i_t(K_δ,n−δ)x^t with equality if and only if G=K_δ,n−δ.     

A relative bound for independence

We prove an upper bound for the independence number of a graph in terms of the largest Laplacian eigenvalue, and of a certain induced subgraph. Our bound is a refinement of a well-known Hoffman-type bound.     

On the independence complex of square grids

The enumeration of independent sets of regular graphs is of interest in statistical mechanics, as it corresponds to the solution of hard-particle models. In 2004, it was conjectured by Fendley et al., that for some rectangular grids, with toric boundary conditions, the alternating number of independent sets is extremely simple. More precisely, under a coprimality condition on the sides of the rectangle, the number of independent sets of even and odd cardinality always differ by 1. In physics terms, this means looking at the hard-particle model on these grids at activity −1. This conjecture was recently proved by Jonsson. Here we produce other families of grid graphs, with open or cylindric boundary conditions, for which similar properties hold without any size restriction: the number of independent sets of even and odd cardinality always differ by 0, ±1, or, in the cylindric case, by some power of 2. We show that these results reflect a stronger property of the independence complexes of our graphs. We determine the homotopy type of these complexes using Forman’s discrete Morse theory. We find that these complexes are either contractible, or homotopic to a sphere, or, in the cylindric case, to a wedge of spheres. Finally, we use our enumerative results to determine the spectra of certain transfer matrices describing the hard-particle model on our graphs at activity −1. These results parallel certain conjectures of Fendley et al., proved by Jonsson in the toric case.     

Independence number of de Bruijn graphs

In this paper, we give several exact values of the independence number of a de Bruijn graph UB(d,D) and in the other cases, we establish pertinent lower and upper bounds of this parameter. We show that asymptotically, if d is even, the ratio of the number of vertices of a greatest independent set of UB(d,D) is .     

Graph polynomials from principal pivoting

The recursive computation of the interlace polynomial introduced by Arratia, Bollobás and Sorkin is defined in terms of a new pivoting operation on undirected simple graphs. In this paper, we interpret the new pivoting operation on graphs in terms of standard pivoting (on matrices). Specifically, we show that, up to swapping vertex labels, Arratia et al.'s pivoting operation on a graph is equivalent to a principal pivot transform on the graph's adjacency matrix, provided that all computations are performed in the Galois field F₂. Principal pivoting on adjacency matrices over F₂ has a natural counterpart on isotropic systems. Thus, our view of the interlace polynomial is closely related to the one by Aigner and van der Holst.The observations that adjacency matrices of undirected simple graphs are skew-symmetric in F₂ and that principal pivoting preserves skew-symmetry in all fields suggest to extend Arratia et al.'s pivoting operation to fields other than F₂. Thus, the interlace polynomial extends to polynomials on gain graphs, namely bidirected edge-weighted graphs whereby reversed edges carry non-zero weights that differ only by their sign. Extending a proof by Aigner and van der Holst, we show that the extended interlace polynomial can be represented in a non-recursive form analogous to the non-recursive form of the original interlace polynomial, i.e., the Martin polynomial.For infinite fields it is shown that the extended interlace polynomial does not depend on the (non-zero) gains, as long as they obey a non-singularity condition. These gain graphs are all supported by a single undirected simple graph. Thus, a new graph polynomial is defined for undirected simple graphs. The recursive computation of the new polynomial can be done such that all ends of the recursion correspond to independent sets. Moreover, its degree equals the independence number. However, the new graph polynomial is different from the independence polynomial.