The kth lower bases of primitive non-powerful signed digraphs

In [J. Shao, L. You, H. Shan, Bound on the bases of irreducible generalized sign pattern matrices, Linear Algebra Appl. 427 (2007) 285-300], the authors extended the concept of the base from powerful sign pattern matrices to non-powerful irreducible sign pattern matrices. Recently, the kth local bases and the kth upper bases, which are generalizations of the bases, of primitive non-powerful signed digraphs were introduced. In this paper, we introduce a new parameter called the kth lower bases of primitive non-powerful signed digraphs and obtain some bounds for it. For some cases, the bounds we obtain are best possible and the extremal signed digraphs are characterized, respectively. Moreover, we show that there exist “gaps” in the kth lower bases set of primitive non-powerful signed digraphs.     

The Generalized <Emphasis Type="Italic">τ</Emphasis>-Bases of Primitive Non-Powerful Signed Digraphs with d Loops

Let n, k, τ, d be positive integers with 1 ≤ k, τ, d ≤ n. As natural extensions of the bases, the kth local bases, the kth upper bases and the kth lower bases of primitive non-powerful signed digraphs, we introduce a number of new, though, intimately related parameters called the generalized τ-bases of primitive non-powerful signed digraphs. Moreover, some sharp bounds for the generalized τ-bases of primitive non-powerful signed digraphs with n vertices and d loops are obtained, respectively.     

Bounds on the k-th generalized base of a primitive sign pattern matrix

You et al. [L. You, J. Shao, and H. Shan, Bounds on the bases of irreducible generalized sign pattern matrices, Lin. Alg. Appl. 427 (2007), pp. 285–300] extended the concept of the base of a powerful sign pattern matrix to the nonpowerful, irreducible sign pattern matrices. The key to their generalization was to view the relationship A ^l =A ^l?+?p as an equality of generalized sign patterns rather than of sign patterns. You, Shao and Shan showed that for primitive generalized sign patterns, the base is the smallest positive integer k such that all entries of A ^k are ambiguous. In this paper we study the k-th generalized base for nonpowerful primitive sign pattern matrices. For a primitive, nonpowerful sign pattern A, this is the smallest positive integer h such that A^k has h rows consisting entirely of ambiguous entries. Extending the work of You, Shao and Shan, we obtain sharp upper bounds on the k-th generalized base, together with a complete characterization of the equality cases for those bounds. We also show that there exist gaps in the k-th generalized base set of the classes of such matrices.     

一类特殊的本原不可幂对称带号有向图的基指数的上界

一个本原不可幂带号有向图s的基指数l(s)是这样的最小正整数l,使得在s中,从任意一点u到任意一点v都有一对长为l的sssD途径.本文研究了n阶最小奇圈长为r的本原不可幂对称带号有向图的基指数,给出了这类有向图的基指数的最大值.     

Gaps in the base set of primitive nonpowerful sign patterns

For a primitive nonpowerful square sign pattern A, the base of A, denoted by l(A), is the least positive integer l such that every entry of A ^l is #. In this article, we consider the base set of the primitive nonpowerful sign pattern matrices. Some useful results about the bases for the sign pattern matrices are presented there. Some special sign pattern matrices with given bases are characterized and more ‘gaps’ in the base set are shown.     

本原对称无环带号有向图的基指数与基指数集

In this paper,we study the bases and base sets of primitive symmetric loop-free (generalized)signed digraphs on n vertices.We obtain sharp upper bounds of the bases,and show that the base sets of the classes of such digraphs are{2,3,...,2n-1}.We also give a new proof of an important result obtained by Cheng and Liu.     

Bounds on the local bases of primitive nonpowerful nearly reducible sign patterns

In this work, we study the kth local base, which is a generalization of the base, of a primitive non-powerful nearly reducible sign pattern of order n ≥ 7. We obtain the sharp bound together with a complete characterization of the equality case, of the kth local bases for primitive non-powerful nearly reducible sign patterns. We also show that there exist “gaps” in the kth local base set of primitive non-powerful nearly reducible sign patterns.     

Local bases of primitive non-powerful signed digraphs

In 1994, Z. Li, F. Hall and C. Eschenbach extended the concept of the index of convergence from nonnegative matrices to powerful sign pattern matrices. Recently, Jiayu Shao and Lihua You studied the bases of non-powerful irreducible sign pattern matrices. In this paper, the local bases, which are generalizations of the base, of primitive non-powerful signed digraphs are introduced, and sharp bounds for local bases of primitive non-powerful signed digraphs are obtained. Furthermore, extremal digraphs are described.     

具有第二大基指数的本原对称带号有向图的刻画

Recently, the primitive symmetric signed digraphs on n vertices with the maximum base 2n and the primitive symmetric loop-free signed digraphs on n vertices with the maximum base 2n-1 are characterized, respectively. In this paper, the primitive symmetric signed digraphs with loops on n vertices with the base 2n-1 are characterized, and then the primitive symmetric signed digraphs on n vertices with the second maximum base 2n-1 are characterized.     

Coefficients of ergodicity and the scrambling index

For a primitive stochastic matrix S, upper bounds on the second largest modulus of an eigenvalue of S are very important, because they determine the asymptotic rate of convergence of the sequence of powers of the corresponding matrix. In this paper, we introduce the definition of the scrambling index for a primitive digraph. The scrambling index of a primitive digraph D 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; it is denoted by k(D). We investigate the scrambling index for primitive digraphs, and give an upper bound on the scrambling index of a primitive digraph in terms of the order and the girth of the digraph. By doing so we provide an attainable upper bound on the second largest modulus of eigenvalues of a primitive matrix that make use of the scrambling index.     

The signed <Emphasis Type="Italic">k</Emphasis>-domination number of directed graphs

Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d _D ⁻ ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N ⁻[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $ \sum\nolimits_{v \in V} {f(v)} $ \sum\nolimits_{v \in V} {f(v)} . The signed k-domination number for a digraph D is γ _kS (D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γ _kS (D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.     

Bounds on the kth multi-g base index of nearly reducible sign pattern matrices

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.     

Lower bounds of the Laplacian graph eigenvalues

In this paper we prove that all positive eigenvalues of the Laplacian of an arbitrary simple graph have some positive lower bounds. For a fixed integer k 1 we call a graph without isolated vertices k-minimal if its kth greatest Laplacian eigenvalue reaches this lower bound. We describe all 1-minimal and 2-minimal graphs and we prove that for every k 3 the path P_k+1 on k + 1 vertices is the unique k-minimal graph.     

Exponents of a class of two-colored digraphs

A two-colored digraph D is primitive if there exist nonnegative integers h and k with h+k>0 such that for each pair (i, j) of vertices there exists an (h, k)-walk in D from i to j. The exponent of the primitive two-colored digraph D is the minimum value of h+k taken over all such h and k. In this article, we consider special primitive two-colored digraphs whose uncolored digraph has n+s vertices and consist of one n-cycle and one (n???2)-cycle. We give the bounds on the exponents, and the characterizations of the extremal two-colored digraphs.     

Primitive non-powerful symmetric loop-free signed digraphs with given base and minimum number of arcs

In [B.M. Kim, B.C. Song, W. Hwang, Primitive graphs with given exponents and minimum number of edges, Linear Algebra Appl. 420 (2007) 648-662], the minimum number of edges of a simple graph on n vertices with exponent k was determined. In this paper, we completely determine the minimum number, H(n,k), of arcs of primitive non-powerful symmetric loop-free signed digraphs on n vertices with base k, characterize the underlying digraphs which have H(n,k) arcs when k is 2, nearly characterize the case when k is 3 and propose an open problem.     

Maximally connected digraphs

This paper introduces a new parameter I = I(G) for a loopless digraph G, which can be thought of as a generalization of the girth of a graph. Let k, λ, δ, and D denote respectively the connectivity, arc-connectivity, minimum degree, and diameter of G. Then it is proved that λ = δ if D ? 2I and κ k = δ if D ? 2I - 1. Analogous results involving upper bounds for k and λ are given for the more general class of digraphs with loops. Sufficient conditions for a digraph to be super-λ and super-k are also given. As a corollary, maximally connected and superconnected iterated line digraphs and (undirected) graphs are characterized.     

HSAGA and its application for the construction of near-Moore digraphs

The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and given diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimal solutions.This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct large digraphs. We present our new results obtained by HSAGA, as well as several related open problems.     

Diameter increase caused by edge deletion

We consider the following problem: Given positive integers k and D, what is the maximum diameter of the graph obtained by deleting k edges from a graph G with diameter D, assuming that the resulting graph is still connected? For undirected graphs G we prove an upper bound of (k + 1)D and a lower bound of (k + 1)D ? k for even D and of (k + 1)D ? 2k + 2 for odd D ? 3. For the special cases of k = 2 and k = 3, we derive the exact bounds of 3D ? 1 and 4D ? 2, respectively. For D = 2 we prove exact bounds of k + 2 and k + 3, for k ? 4 and k = 6, and k = 5 and k ? 7, respectively. For the special case of D = 1 we derive an exact bound on the resulting maximum diameter of order θ(√k). For directed graphs G, the bounds depend strongly on D: for D = 1 and D = 2 we derive exact bounds of θ(√k) and of 2k + 2, respectively, while for D ? 3 the resulting diameter is in general unbounded in terms of k and D. Finally, we prove several related problems NP-complete.     

Lotto design tables

An LD(n,k,p,t;b) lotto design is a set of b k‐sets (blocks) of an n‐set such that any p‐set intersects at least one k‐set in t or more elements. Let L(n,k,p,t) denote the minimum number of blocks in any LD(n,k,p,t;b) lotto design. We will list the known lower and upper bound theorems for lotto designs. Since many of these bounds are recursive, we will incorporate this information in a set of tables for lower and upper bounds for lotto designs with small parameters. We will also use back‐track algorithms, greedy algorithms, and simulated annealing to improve the tables. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 335–359, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10020