Search

In 2010, Huang and Liu introduced a useful parameter called the generalized μ-scrambling indices of a primitive digraph. In this paper, we give some bounds for μ-scrambling indices of some primitive digraphs with d loops and the digraphs attained the sharp upper bounds are provided.

Let H $\mathcal{H}$ be a k-uniform hypergraph on n vertices with degree sequence Δ=d1≥⋯≥dn=δ $\Delta=d_{1} \geq\cdots\geq d_{n}=\delta$. In this paper, in terms of degree di $d_{i}$, we give a new upper bound for the Z-spectral radius of the adjacency tensor of H $\mathcal{H}$. Some examples are given to show the efficiency of the bound.

This paper deals with roommate problems (Gale and Shapley, Am Math Mon 69(1):9–15, 1962) that are solvable, i.e., have a non-empty core (set of stable matchings). We study rank-fairness within pairs of stable matchings and the size of the core by means of maximal and average rank gaps. We provide upper bounds in terms of maximal and average disagreements in the agents’ rankings. Finally, we show that most of our bounds are tight., The first draft of this paper was written while F. Klijn was visiting Universidad del Rosario. He gratefully acknowledges the hospitality of Universidad del Rosario and support from AGAUR-Generalitat de Catalunya (2014-SGR-1064 and 2017-SGR-1359), the Spanish Ministry of Economy and Competitiveness through Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 (ECO2014-59302-P and ECO2017-88130-P), and the Severo Ochoa Programme for Centres of Excellence in R&D (SEV-2015-0563).

A hypergraph H = ( V , &epsilon, ) is a pair consisting of a vertex set V , and a set &epsilon, of subsets (the hyperedges of H ) of V . A hypergraph H is r -uniform if all the hyperedges of H have the same cardinality r . Let H be an r -uniform hypergraph, we generalize the concept of trees for r -uniform hypergraphs. We say that an r -uniform hypergraph H is a generalized hypertree ( G H T ) if H is disconnected after removing any hyperedge E , and the number of components of G H T &minus, E is a fixed value k &nbsp, ( 2 &le, k &le, r ) . We focus on the case that G H T &minus, E has exactly two components. An edge-minimal G H T is a G H T whose edge set is minimal with respect to inclusion. After considering these definitions, we show that an r -uniform G H T on n vertices has at least 2 n / ( r + 1 ) edges and it has at most n &minus, r + 1 edges if r &ge, 3 &nbsp, and &nbsp, n &ge, 3 , and the lower and upper bounds on the edge number are sharp. We then discuss the case that G H T &minus, E has exactly k &nbsp, r &minus, 1 ) components.

Dynamic systems described by fc(z) = z2 + c is called Mandelbrot set (M-set), which is important for fractal and chaos theories due to its simple expression and complex structure. fc(z) = zk + c is called generalized M set (k–M set). This paper proposes a new theory to compute the higher and lower bounds of generalized M set while exponent k is rational, and proves relevant properties, such as that generalized M set could cover whole complex number plane when k < 1, and that boundary of generalized M set ranges from complex number plane to circle with radius 1 when k ranges from 1 to infinite large. This paper explores fractal characteristics of generalized M set, such as that the boundary of k–M set is determined by k, when k = p/q, where p and q are irreducible integers, (GCD(p, q) = 1, k > 1), and that k–M set can be divided into |p–q| isomorphic parts.

In the article, we present the necessary and sufficient condition for the parameter p on the interval $(7/5, \infty)$ such that the function $x\rightarrow\operatorname{erf}(x)/B_{p}(x)$ is strictly increasing (decreasing) on $(0, \infty)$ , and find the best possible parameters p, q on the interval $(7/5, \infty)$ such that the double inequality $B_{p}(x)0$ , where $\operatorname{erf}(x)=2\int_{0}^{x}e^{-t^{2}}\,dt/\sqrt{\pi}$ is the error function, $B_{p}(x)=\sqrt{1-\lambda(p)e^{-px^{2}}-[1-\lambda(p)]e^{-\mu(p)x^{2}}}$ , $\lambda(p)=16(5p-7)/[(15p^{2}-40p+28)(45p^{2}-60p-4)]$ and $\mu(p)=4(5p-7)/[5(3p-4)]$ .

It was proved by Hoeffding in 1963 that a real random variable X confined to [a, b] satisfies E e^(X--E X) $\le$ e^((b--a)^2/8). We generalise this to complex random variables., Electronic Communications in Probability, Institute of Mathematical Statistics (IMS), 2016

Let G be a simple graph of order n , and let μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n = 0 be the Laplacian spectrum of G . The Laplacian-energy-like invariant of G ( LEL for short) is defined as LEL ( G ) = ∑ i = 1 n - 1 μ i . In this paper, a new lower bound for LEL of graphs in terms of the maximum degree is given. Meanwhile, an upper bound and a lower bound for LEL of the line graph (resp., the subdivision graph and the total graph) of a regular graph G are obtained.

In this paper, we continue the study of locating-total domination in graphs, introduced by Haynes et al. [T.W. Haynes, M.A. Henning, J. Howard, Locating and total dominating sets in trees, Discrete Applied Mathematics 154 (8) (2006) 1293-1300]. A total dominating set S in a graph G=(V,E) is a locating-total dominating set of G if, for every pair of distinct vertices u and v in V-S, N"G(u)@?S N"G(v)@?S. The minimum cardinality of a locating-total dominating set is the locating-total domination number @c"t^L(G). We show that, for a tree T of order n>=3 with l leaves and s support vertices, n+l+12-s@?@c"t^L(T)@?n+l2. Moreover, we constructively characterize the extremal trees achieving these bounds.

Let G be a simple graph with vertices v 1 , v 2 , ⋯ , v n , of degrees Δ = d 1 ⩾ d 2 ⩾ ⋯ ⩾ d n = δ , respectively. Let A be the ( 0 , 1 ) -adjacency matrix of G and D be the diagonal matrix diag ( d 1 , d 2 , ⋯ , d n ) . Q ( G ) = D + A is called the signless Laplacian of G. In this paper, we give some sharp bounds on signless Laplacian spectral radius ρ ( Q ( G ) ) in terms of d i .

This paper is concerned with the bounds of the Perron root @r(A) of a nonnegative irreducible matrix A. Two new methods utilizing the relationship between the Perron root of a nonnegative irreducible matrix and its generalized Perron complements are presented. The former method is efficient because it gives the bounds for @r(A) only by calculating the row sums of the generalized Perron complement P"t(A/A[@a]) or even the row sums of submatrices A[@a],A[@b],A[@a,@b] and A[@b,@a]. And the latter gives the closest bounds (just in this paper) of @r(A). The results obtained by these methods largely improve the classical bounds. Numerical examples are given to illustrate the procedure and compare it with others, which shows that these methods are effective.

Let H ( λ ) = − Δ + λ b be a discrete Schrodinger operator on l 2 ( Z d ) with a potential b and a non-negative coupling constant λ. When b ≡ 0 , it is well known that σ ( − Δ ) = [ 0 , 4 d ] . When b ≢ 0 , let s ( − Δ + λ b ) : = inf σ ( − Δ + λ b ) and M ( − Δ + λ b ) : = sup σ ( − Δ + λ b ) be the bounds of the spectrum of the Schrodinger operator. One of the aims of this paper is to study the influence of the potential b on the bounds 0 and 4d of the spectrum of −Δ. More precisely, we give a necessary and sufficient condition on the potential b such that s ( − Δ + λ b ) is strictly positive for λ small enough. We obtain a similar necessary and sufficient condition on the potential b such that M ( − Δ + λ b ) is lower than 4d for λ small enough. In dimensions d = 1 and d = 2 , the situation is more precise. The following result was proved by Killip and Simon (2003) (for d = 1 ) in [5] , then by Damanik et al. (2003) (for d = 1 and d = 2 ) in [3] : If σ ( − Δ + b ) ⊂ [ 0 , 4 d ] , then b ≡ 0 . Our study on the bounds of the spectrum of ( − Δ + b ) allows us to give a different and easy proof to this result.

In this paper, we present some sharp upper bounds for the number of spanning trees of a connected graph in terms of its structural parameters such as the number of vertices, the number of edges, maximum vertex degree, minimum vertex degree, connectivity and chromatic number.

Let T n + be the set of all trees of order n with perfect matchings. In this paper, we prove that for any tree T ∈ T n + , its k th largest Laplacian eigenvalue μ k ( T ) satisfies μ k ( T ) = 2 when n = 2 k , and μ k ( T ) ⩽ ⌈ n 2 k ⌉ + 2 + ( ⌈ n 2 k ⌉ ) 2 + 4 2 when n ≠ 2 k . Moreover, this upper bound is sharp when n = 0 ( mod 2 k ) .

We study the state complexity of certain simple languages. If A is an alphabet of k letters, then a k-language is a nonempty set of words of length k, that is, a uniform language of length k. We show that the minimal state complexity of a k-language is k+2, and the maximal, (k^k^-^1-1)/(k-1)+2^k+1. We prove constructively that, for every i between the minimal and maximal bounds, there is a language of state complexity i. We introduce a class of automata accepting sets of words that are permutations of A; these languages define a complete hierarchy of complexities between k^2-k+3 and 2^k+1. The languages of another class of automata, based on k-ary trees, define a complete hierarchy of complexities between 2^k+1 and (k^k^-^1-1)/(k-1)+2^k+1. This provides new examples of uniform languages of maximal complexity.

Let G = ( V , E ) be a digraph with n vertices and m arcs without loops and multiarcs. The spectral radius ρ ( G ) of G is the largest eigenvalue of its adjacency matrix. In this paper, the following sharp bounds on ρ ( G ) have been obtained. min { t i + t j + : ( v i , v j ) ∈ E } ⩽ ρ ( G ) ⩽ max { t i + t j + : ( v i , v j ) ∈ E } where G is strongly connected and t i + is the average 2-outdegree of vertex v i . Moreover, each equality holds if and only if G is average 2-outdegree regular or average 2-outdegree semiregular.

In this paper the conjecture on kth lower multiexponent of primitive matrices proposed by R.A. Brualdi and Liu are partly proved.

In [J.Y. Shao, L.H. You, Bound on the base of irreducible generalized sign pattern matrices, Discrete Math., in press], Shao and You extended the concept of the base from powerful sign pattern matrices to non-powerful (and generalized) sign pattern matrices. In this paper, we study the base for primitive non-powerful nearly reducible sign pattern (and generalized sign pattern) matrices. We obtain sharp upper bounds, together with complete characterization of the equality cases of the base for primitive nearly reducible sign pattern (and generalized sign pattern) matrices. We also show that there exist “gaps” in the base set of the classes of such matrices.

A Roman dominating function (or just RDF) on a graph G = (V,E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = Pu2V (G) f(u). The Roman domination number of a graph G, denoted by R(G), is the minimum weight of a Roman dominating function on G. A graph G is Roman domination stable if the Roman domination number of G remains unchanged under removal of any vertex. In this paper we present upper bounds for the Roman domination number in the class of Roman domination stable graphs, improving bounds posed in [V. Samodivkin, Roman domination in graphs: the class RUV R, Discrete Math. Algorithms Appl. 8 (2016) 1650049].

The harmonic index of a graph $G$ is defined as the sum of weights $\frac{2}{d(v_i)+d(v_j)}$ of all edges $v_iv_j$ of $G$, where $d(v_i)$ denotes the degree of the vertex $v_i$ in $G$. In this paper, we study how the harmonic index behaves when the graph is under perturbations. These results are used to provide a simpler method for determining the unicyclic graphs with maximum and minimum harmonic index among all unicyclic graphs, respectively. Moreover, a lower bound for harmonic index is also obtained.

In this paper, an upper bound and a tight lower bound for the second largest eigenvalue of a tree with perfect matchings are obtained. At the same time, a lower bound for the maximum value of the second largest eigenvalue of trees with perfect matchings is also given.

We sketch the ideas in the proofs of results on Ramsey numbers of a cycle, particularly in many colors, in which one is due to professor Ko-Wei Lih and the author for the right order of magnitude of Ramsey number $r_k(C_{2m})$ as $k\to\infty$ for $m=2,3,5$.

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex vi by d(vi). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v1),d(v2),…,d(vn)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q1(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q1(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q1(G). Then we present three sharp lower bounds for q1(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.

The Randić index R(G) of a graph G is defined by R(G)=∑uv1d(u)d(v), where d(u) is the degree of a vertex u in G and the summation extends over all edges uv of G. In this work, we give a sharp upper bound and a lower bound of the Randić index among connected n-vertex graphs with girth g≥k(k≥3).

Let D(G)=(d"i","j)"n"x"n denote the distance matrix of a connected graph G with order n, where d"i"j is equal to the distance between vertices v"i and v"j in G. The value D"[email protected]?"j"="1^nd"i"j (i=1,2,...,n) is called the distance degree of vertex v"i. Denote by @r(G),@r"n(G) the largest eigenvalue and the smallest eigenvalue of D(G) respectively. The distance spectral spread of a graph G is defined to be S"D(G)[email protected](G)[email protected]"n(G). In this paper, some lower bounds on S"D(G) are given in terms of distance degrees, the largest vertex degree and clique number; the spreads of K"n, K"@?"n"2"@?","@?"n"2"@?, K"n"-"@[email protected][email protected]"1, K"1","n"-"1 are proved to be the least among all connected graphs with n vertices, all bipartite graphs with n vertices, all the graphs with both n vertices and independent number @a, all trees with n vertices respectively.

In 2009, Akelbek and Kirkland introduced a useful parameter called the scrambling index of a primitive digraph D, which is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k. In this paper, we obtain some new upper bounds for the scrambling index of primitive digraphs. Moreover, the maximum index problem, the extremal matrix problem and the index set problem for the scrambling index of various classes of primitive digraphs (e.g. primitive digraphs with d loops, minimally strong digraphs, nearly decomposable digraphs, micro-symmetric digraphs, etc.) are settled, respectively.

Li et al. [On the period and base of a sign pattern matrix, Linear Algebra Appl. 212/213 (1994) 101–120.] extended the concepts of the base and period from nonnegative matrices to powerful sign pattern matrices. Then, Shao and You [Bound on the basis of irreducible generalized sign pattern matrices, Linear Algebra Appl. 427 (2007) 285–300.] extended the concepts of the base from powerful sign pattern matrices to non-powerful irreducible sign pattern matrices. In this paper we mainly study the kth multi-g base index for non-powerful primitive nearly reducible sign pattern matrices. We obtain sharp upper bounds, together with a complete characterization of the equality cases of the kth multi-g base index for primitive nearly reducible generalized sign pattern matrices. We also show that there exist “gaps” in the kth multi-g base index set of the classes of such matrices.

The paper reviews some of the existing exact bounds to the maximum clique of a graph and successively presents a new upper and a new lower bound. The new upper bound is ω ≤ n - rank oA/2, where oA is the adjacency matrix of the complementary graph, and derives from a formulation of the maximum clique problem in complex space. The new lower bound is ω ≥ 1/(1 - gj*(α*)) (see text for details) and improves strictly the present best lower bound published by Wilf (J. Combin. Theory Ser. B 40 (1986) 113).Throughout the paper an eye is kept on the computational complexity of actually calculating the bounds. At the end, the various bounds are compared on 700 random graphs.

We extend the well-known Chebyshev’s inequality to some new cases involving permanents under the proper hypotheses. Our main results are per ( A ⊙ B ) n ! ⩾ per A n ! · per B n ! and per A ∏ i = 1 n ∑ j = 1 n a i , j ⩽ per B ∏ i = 1 n ∑ j = 1 n b i , j . As applications, we consider the problem of finding bounds of the ratios of two functions involving permanents.

The traveling salesman problem (TSP) is one of the best-known combinatorial optimization problems. Branch-and-bound (BnB) is the best method for finding an optimal solution of the TSP. Previous research has shown that there exists a transition in the average computational complexity of BnB on random trees. We show experimentally that when the intercity distances of the asymmetric TSP are drawn uniformly from 0,1,2,…, r , the complexity of BnB experiences an easy-hard transition as r increases. We also observe easy-hard-easy complexity transitions when asymmetric intercity distances are chosen from a log-normal distribution. This transition pattern is similar to one previously observed on the symmetric TSP. We then explain these different transition patterns by showing that the control parameter that determines the complexity is the number of distinct intercity distances.

The general renewal equation and real variable methods are used to show that for a renewal process with generic lifetime random variable $X \geqq 0$ having distribution $F$ and finite first and second moments $EX = \lambda^{-1}$ and $EX^2$, the renewal function $U(x) = \sum^\infty_0 F^{n^\ast(x)$ satisfies $U(x) \leqq \lambda x_+ + C\lambda^2EX^2$ for a certain constant $C$ independent of $F$. Stone (1972) showed that $1 \leqq C \leqq 2.847 \cdots$; it is proved here that $C \leqq 1.3186 \cdots$ and conjectured that $C = 1$.