The maximum Perron roots of digraphs with some given parameters

We characterize the extremal digraphs which attain the maximum Perron root of digraphs with given arc connectivity and number of vertices. We also characterize the extremal digraphs which attain the maximum Perron root of digraphs given diameter and number of vertices.     

FINITENESS CONDITIONS FOR GENERALIZED EXPONENTS OF DIGRAPHS

1.IntroductionR.A.BrualdiandBolianLiuintroducedin199011]theconceptofgeneralizedexponentsforprimitivedigraphs.Thisconceptisageneralizationofthetraditionalconceptoftheexponentsforprimitivedigraphsandhasbackgroundsinmemorylesscommunicationsystemsassociatedwithdigraphs.Inthispaperweshowthatgeneralizedexponentscanalsobedefinedfordigraphswhicharenotnecessarilyprimitive.WewillgivenecessaryandsufficientconditionsforthefinitenessofthegeneralizedexponentsexpD(k),f(D,k)andF(D,k).Theseideasandresultss…     

Packing strong subgraph in digraphs

In this paper, we study two types of strong subgraph packing problems in digraphs, including internally disjoint strong subgraph packing problem and arc-disjoint strong subgraph packing problem. These problems can be viewed as generalizations of the famous Steiner tree packing problem and are closely related to the strong arc decomposition problem. We first prove the NP-completeness for the internally disjoint strong subgraph packing problem restricted to symmetric digraphs and Eulerian digraphs. Then we get inapproximability results for the arc-disjoint strong subgraph packing problem and the internally disjoint strong subgraph packing problem. Finally we study the arc-disjoint strong subgraph packing problem restricted to digraph compositions and obtain some algorithmic results by utilizing the structural properties.     

The number of reachable pairs in a digraph

For a digraph G, let R(G) (respectively, R^(k)(G)) be the number of ordered pairs (u,v) of vertices of G such that u≠v and v is reachable from u (respectively, reachable from u by a path of length ?k). In this paper, we study the range S_n of R(G) and the range of R^(k)(G) as G varies over all possible digraphs on n vertices. We give a sufficient condition and a necessary condition for an integer to belong to S_n. These determine the set S_n for all n?208. We also determine for k?4 and show that whenever n?k+(k+1)^0.57+2, for arbitrary k.     

A new Bartholdi zeta function of a digraph II

We introduce a new type of the Bartholdi zeta function of a digraph D. Furthermore, we define a new type of the Bartholdi L-function of D, and give a determinant expression of it. We show that this L-function of D is equal to the L-function of D defined in [H. Mizuno, I. Sato, A new Bartholdi zeta function of a digraph, Linear Algebra Appl. 423 (2007) 498-511]. As a corollary, we obtain a decomposition formula for a new type of the Bartholdi zeta function of a group covering of D by new Bartholdi L-functions of D.     

On the generalized indices of boolean matrices

We characterize completely those Boolean matrices with the largest generalized indices in the class of Boolean matrices and in the class of reducible Boolean matrices and derive a new upper bound for the generalized index in terms of period. We also generalize the upper and lower multiexponents of primitive Boolean matrices to general Boolean matrices.     

The complexity of locally injective homomorphisms

A homomorphism f:G→H, from a digraph G to a digraph H, is locally injective if the restriction of f to N⁻(v) is an injective mapping, for each v∈V(G). The problem of deciding whether such an f exists is known as the injective H-colouring problem (INJ-HOM_H). In this paper, we classify the problem INJ-HOM_H as being either a problem in P or a problem that is NP-complete. This is done in the case where H is a reflexive digraph (i.e. H has a loop at every vertex) and in the case where H is an irreflexive tournament. A full classification in the irreflexive case seems hard, and we provide some evidence as to why this may be the case.     

Some approaches to a conjecture on short cycles in digraphs

We consider the following special case of a conjecture due to Caccetta and Häggkvist: Let D be a digraph on n vertices that all have in-degree and out-degree at least n/3. Then, D contains a directed cycle of length 2 or 3. We discuss several necessary conditions for possible counterexamples to this conjecture, in terms of cycle structure, diameter, maximum degree, clique number, toughness, and local structure. These conditions have not enabled us to prove or refute the conjecture, but they lead to proofs of special instances of the conjecture.     

Spectral Radius of Non-negative Matrices and Digraphs

We present an upper and a lower bound for the spectral radius of non-negative matrices. Then we give the bounds for the spectral radius of digraphs. Received February 10, 1999, Revised November 13, 2000, Accepted March 5, 2001