共查询到20条相似文献,搜索用时 0 毫秒
1.
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. 相似文献
2.
《Discrete Mathematics》2023,346(1):113143
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. 相似文献
3.
《Discrete Mathematics》2021,344(12):112605
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. 相似文献
4.
The independence polynomial, ω(G,x)=∑wkxk, of a graph, G, has coefficients, wk, 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 wk≠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 wk 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. 相似文献
5.
《Discrete Mathematics》2019,342(1):18-28
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. 相似文献
6.
Y. Manoussakis 《Graphs and Combinatorics》2009,25(3):377-384
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. 相似文献
7.
Feng Qi Da-Wei Niu Dongkyu Lim Bai-Ni Guo 《Mathematical Methods in the Applied Sciences》2020,43(6):2967-2983
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. 相似文献
8.
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. 相似文献
9.
Gradimir V. Milovanovi? Aleksandar S. Cvetkovi? 《Journal of Mathematical Analysis and Applications》2005,311(1):191-208
We present some sharp inequalities for symmetric functions and give an application to orthogonal polynomials. 相似文献
10.
The independence polynomial of a graph is the generating function of the numbers of independent sets of each size. A graph of order is very well-covered if every maximal independent set has size . 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. 相似文献
11.
Closed expressions are obtained for derivatives of symbolic order with respect to parameters for the hypergeometric functions, Laguerre, Gegenbauer, Jacobi and some other polynomial. 相似文献
12.
Bruce Curry 《Computational Management Science》2007,4(3):227-242
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.
相似文献
13.
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}. 相似文献
14.
15.
16.
V. A. Yudin 《Mathematical Notes》2007,82(3-4):564-568
In the space of continuous functions defined on the ball from ?n, n ≥ 2, we study the set of algebraic polynomials of least deviation from zero. Its width and dimension are estimated. 相似文献
18.
In this paper, we present several necessary conditions for the reversed Dickson polynomial of the second kind to be a permutation of . In particular, we give explicit evaluation of the sum . 相似文献
19.
20.
E. G. Kir’yatskiĭ 《Siberian Mathematical Journal》2009,50(3):456-466
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. 相似文献