Well-covered circulant graphs

A graph is well-covered if every independent set can be extended to a maximum independent set. We show that it is co-NP-complete to determine whether an arbitrary graph is well-covered, even when restricted to the family of circulant graphs. Despite the intractability of characterizing the complete set of well-covered circulant graphs, we apply the theory of independence polynomials to show that several families of circulants are indeed well-covered. Since the lexicographic product of two well-covered circulants is also a well-covered circulant, our partial characterization theorems enable us to generate infinitely many families of well-covered circulants previously unknown in the literature.     

Independence equivalence classes of paths

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. A graph whose independence equivalence class contains only itself, up to isomorphism, is independence unique. Beaton, Brown and Cameron [2] showed that paths with an odd number of vertices are independence unique and raised the problem of finding the independence equivalence class of paths with an even number of vertices. The problem is completely solved in this paper.     

Independence equivalence classes of cycles

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. Beaton, Brown and Cameron (2019) found the independence equivalence classes of even cycles, and raised the problem of finding the independence equivalence class of odd cycles. The problem is completely solved in this paper.     

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.     

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.     

Longest Cycles in 3-connected Graphs with Given Independence Number

Fouquet and Jolivet conjectured that a k-connected graph of order n and independence number α ≥ k has a cycle of length at least [Fouquet and Jolivet, Problèmes combinatoires et théorie des graphes Orsay (1976), Problems, page 438]. Here we prove this conjecture for k=3.     

Some properties and an application of multivariate exponential polynomials

In the paper, the authors introduce a notion “multivariate exponential polynomials” which generalize exponential numbers and polynomials, establish explicit formulas, inversion formulas, and recurrence relations for multivariate exponential polynomials in terms of the Stirling numbers of the first and second kinds with the help of the Faà di Bruno formula, two identities for the Bell polynomials of the second kind, and the inversion theorem for the Stirling numbers of the first and second kinds, construct some determinantal inequalities and product inequalities for multivariate exponential polynomials with the aid of some properties of completely monotonic functions and other known results, derive the logarithmic convexity and logarithmic concavity for multivariate exponential polynomials, and finally find an application of multivariate exponential polynomials to white noise distribution theory by confirming that multivariate exponential polynomials satisfy conditions for sequences required in white noise distribution theory.     

The ridge function representation of polynomials and an application to neural networks

The first goal of this paper is to establish some properties of the ridge function representation for multivariate polynomials, and the second one is to apply these results to the problem of approximation by neural networks. We find that for continuous functions, the rate of approximation obtained by a neural network with one hidden layer is no slower than that of an algebraic polynomial.     

Some inequalities for symmetric functions and an application to orthogonal polynomials

We present some sharp inequalities for symmetric functions and give an application to orthogonal polynomials.     

On the unimodality of independence polynomials of very well-covered graphs

The independence polynomial $i(G,x)$ of a graph $G$ is the generating function of the numbers of independent sets of each size. A graph of order $n$ is very well-covered if every maximal independent set has size $n∕2$. Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials.     

On derivatives of hypergeometric functions and classical polynomials with respect to parameters

Closed expressions are obtained for derivatives of symbolic order with respect to parameters for the hypergeometric functions, Laguerre, Gegenbauer, Jacobi and some other polynomial.     

Parameter redundancy in neural networks: an application of Chebyshev polynomials

This paper deals with feedforward neural networks containing a single hidden layer and with sigmoid/logistic activation function. Training such a network is equivalent to implementing nonlinear regression using a flexible functional form, but the functional form in question is not easy to deal with. The Chebyshev polynomials are suggested as a way forward, providing an approximation to the network which is superior to Taylor series expansions. Application of these approximations suggests that the network is liable to a ‘naturally occurring’ parameter redundancy, which has implications for the training process as well as certain statistical implications. On the other hand, parameter redundancy does not appear to damage the fundamental property of universal approximation.      

An application of Vizing and Vizing-like adjacency lemmas to 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 , where α(G) is the independence number of G. In this note, we apply Vizing and Vizing-like adjacency lemmas to this problem and obtain better bounds for Δ∈{7,…,19}.     

On polynomials of best approximation

In the space of continuous functions defined on the ball from ?ⁿ, n ≥ 2, we study the set of algebraic polynomials of least deviation from zero. Its width and dimension are estimated.     

Necessary conditions for reversed Dickson polynomials of the second kind to be permutational

In this paper, we present several necessary conditions for the reversed Dickson polynomial $E_n(1,x)$ of the second kind to be a permutation of ${\mathbb{F}}_q$. In particular, we give explicit evaluation of the sum ${\sum }_{a\in {\mathbb{F}}_q}{E}_n(1,a)$.     

A family of univalent polynomials in an angular domain

We study the properties of symmetric polynomials of a particular form and use them to find a maximal angular domain of univalence for some family of polynomials.