It is well known that the spectral radius of a tree whose maximum degree is ▫$\Delta$▫ cannot exceed ▫$2\sqrt{\Delta-1}$▫. A similar upper bound holds for arbitrary planar graphs, whose spectral radius cannot exceed ▫$\sqrt{8 \Delta} + 10$▫, and more generally, for all ▫$d$▫-degenerate graphs, where the corresponding upper bound is ▫$\sqrt{4d\Delta}$▫. Following this, we say that a graph ▫$G$▫ is spectrally ▫$d$▫-degenerate if every subgraph ▫$H$▫ of ▫$G$▫ has spectral radius at most ▫$\sqrt{d\Delta(H)}$▫. In this paper we derive a rough converse of the above-mentioned results by proving that each spectrally ▫$d$▫-degenerate graph ▫$G$▫ contains a vertex whose degree is at most ▫$4d\log_2(\Delta(G)/d)$▫ (if ▫$\Delta(G) \ge 2d$▫). It is shown that the dependence on ▫$\Delta$▫ in this upper bound cannot be eliminated, as long as the dependence on ▫$d$▫ is subexponential. It is also proved that the problem of deciding if a graph is spectrally ▫$d$▫-degenerate is co-NP-complete.
COBISS.SI-ID: 16410457
Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this paper we survey the approaches to this central conjecture from domination theory and give some new results along the way. For instance, several new properties of a minimal counterexample to the conjecture are obtained and a lower bound for the domination number is proved for products of claw-free graphs with arbitrary graphs. Open problems, questions and related conjectures are discussed throughout the paper.
COBISS.SI-ID: 16083801
In this paper we study constrained eigenvalue optimization of noncommutative (nc) polynomials, focusing on the polydisc and the ball. Our three main results are as follows: (1) an nc polynomial is nonnegative if and only if it admits a weighted sum of hermitian squares decomposition; (2) (eigenvalue) optima for nc polynomials can be computed using a single semidefinite program (SDP) - this sharply contrasts with the commutative case where sequences of SDPs are needed; (3) the dual solution to this "single" SDP can be exploited to extract eigenvalue optimizers with an algorithm based on two ingredients: solution to a truncated nc moment problem via flat extensions, and Gelfand-Naimark-Segal construction. The implementation of these procedures in our computer algebra system NCSOStools is presented, and several examples pertaining to matrix inequalities are given to illustrate our results.
COBISS.SI-ID: 16276569
In the language of mathematical chemistry, Fibonacci cubes can be defined as the resonance graphs of fibonacenes. Lucas cubes form a symmetrization of Fibonacci cubes and appear as resonance graphs of cyclic polyphenantrenes. In this paper it is proved that the Wiener index of Fibonacci cubes can be written as the sum of products of four Fibonacci numbers which in turn yields a closed formula for the Wiener index of Fibonacci cubes. Asymptotic behavior of the average distance of Fibonacci cubes is obtained. The generating function of the sequence of ordered Hosoya polynomials of Fibonacci cubes is also deduced. Along the way, parallel results for Lucas cubes are given.
COBISS.SI-ID: 16309337