Search

Let A be a nonnegative irreducible matrix of order n and A i (t) be the matrix obtained by increasing its i th diagonal entry by a positive number t. An index i ∈ [ n ] = { 1 , ... , n } is called a universal winner for A , if, letting ρ (⋅) denote the spectral radius, ρ (A i (t)) ≥ ρ (A j (t)) for j ∈ [ n ] and for t ∈ (0 , ∞). Let G be a strongly connected digraph with vertex set [ n ]. Let W G be the set of all nonnegative matrices whose underlying graph structure is G. We say a vertex u structurally dominates another vertex v in G , if ρ (A u (t)) ≥ ρ (A v (t)) for all t ∈ (0 , ∞) and for all A ∈ W G. We characterize the class of digraphs G that do not have a vertex that structurally dominates all other vertices. We say two vertices u and v structurally tie if they structurally dominate each other in G. We supply an equivalent graph theoretic condition for the structural tying of two vertices in G. Let S ⊆ [ n ] be nonempty. We characterize the class of strongly connected digraphs G with vertex set [ n ] such that S is the set of universal winners for each A ∈ W G. We also characterize the strongly connected digraphs whose vertex set can be partitioned into subsets P 1 , P 2 , ... , P k such that vertices inside a part P i structurally tie with each other and vertices of P i structurally dominate vertices of P j strictly (without tying) for i < j. [ABSTRACT FROM AUTHOR]

Calculating single-source shortest paths (SSSPs) rapidly and precisely from weighted digraphs is a crucial problem in graph theory. As a mathematical model of processing uncertain tasks, rough sets theory (RST) has been proven to possess the ability of investigating graph theory problems. Recently, some efficient RST approaches for discovering different subgraphs (e.g. strongly connected components) have been presented. This work was devoted to discovering SSSPs of weighted digraphs by aid of RST. First, SSSPs problem was probed by RST, which aimed at supporting the fundamental theory for taking RST approach to calculate SSSPs from weighted digraphs. Second, a heuristic search strategy was designed. The weights of edges can be served as heuristic information to optimize the search way of $ k $-step $ R $-related set, which is an RST operator. By using heuristic search strategy, some invalid searches can be avoided, thereby the efficiency of discovering SSSPs was promoted. Finally, the W3SP@R algorithm based on RST was presented to calculate SSSPs of weighted digraphs. Related experiments were implemented to verify the W3SP@R algorithm. The result exhibited that W3SP@R can precisely calculate SSSPs with competitive efficiency.

A strongly connected digraph is called a cactoid-type digraph if each of its blocks is a digraph consisting of finitely many oriented cycles sharing a common directed path. In this article, we find the formula for the determinant of the distance matrix for a weighted cactoid-type digraph and find its inverse, whenever it exists. We also compute the determinant of the distance matrix for a class of unweighted and undirected graphs consisting of finitely many cycles, sharing a common path. [ABSTRACT FROM AUTHOR]

The eigenvalues of a digraph are the eigenvalues of its adjacency matrix. The iota energy of a digraph is recently defined as the sum of absolute values of imaginary part of its eigenvalues. In this paper, we extend the concept of iota energy of digraphs to weighted digraphs. We compute the iota energy formulae for the positive and negative weight directed cycles. We also characterize the unicyclic weighted digraphs with cycle weight $ r \in [-1, 1]\backslash \{0\}$ having minimum and maximum iota energy. We obtain well known McClelland upper bound for the iota energy of weighted digraphs. Finally, we find the class of noncospectral equienergetic weighted digraphs.

The energy of a weighted digraph D is the sum of absolute values of real part of its eigenvalues. Recently, the minimal and maximal energy of unicyclic weighted digraphs with cycle weight r ∈ [ − 1 , 1 ] ∖ { 0 } is studied. In this paper, we introduce a class 𝔹 (r , s) of those bicyclic weighted digraphs of fixed order which contain vertex-disjoint weighted cycles of weights r or − r and s or − s , where 0 < r , s ≤ 1. We find digraphs in 𝔹 (r , s) under certain conditions on r and s with extremal energy. [ABSTRACT FROM AUTHOR]

Calculating single-source shortest paths (SSSPs) rapidly and precisely from weighted digraphs is a crucial problem in graph theory. As a mathematical model of processing uncertain tasks, rough sets theory (RST) has been proven to possess the ability of investigating graph theory problems. Recently, some efficient RST approaches for discovering different subgraphs (e.g. strongly connected components) have been presented. This work was devoted to discovering SSSPs of weighted digraphs by aid of RST. First, SSSPs problem was probed by RST, which aimed at supporting the fundamental theory for taking RST approach to calculate SSSPs from weighted digraphs. Second, a heuristic search strategy was designed. The weights of edges can be served as heuristic information to optimize the search way of $ k $-step $ R $-related set, which is an RST operator. By using heuristic search strategy, some invalid searches can be avoided, thereby the efficiency of discovering SSSPs was promoted. Finally, the W3SP@R algorithm based on RST was presented to calculate SSSPs of weighted digraphs. Related experiments were implemented to verify the W3SP@R algorithm. The result exhibited that W3SP@R can precisely calculate SSSPs with competitive efficiency.

Abstract The resistance indices, namely the Kirchhoff index and its generalisations, have undergone intense critical scrutiny in recent years. Based on random walks, we derive three Kirchhoffian indices for strongly connected and weighted digraphs. These indices are expressed in terms of (i) hitting times and (ii) the trace and eigenvalues of suitable matrices associated to the graph, namely the asymmetric Laplacian, the diagonally scaled Laplacian and their Moore–Penrose inverses. The appropriateness of the generalised Kirchhoff index as a measure of network robustness is discussed, providing an alternative interpretation which is supported by an empirical application to the World Trade Network. [ABSTRACT FROM AUTHOR]

The eigenvalues of a digraph are the eigenvalues of its adjacency matrix. The iota energy of a digraph is recently defined as the sum of absolute values of imaginary part of its eigenvalues. In this paper, we extend the concept of iota energy of digraphs to weighted digraphs. We compute the iota energy formulae for the positive and negative weight directed cycles. We also characterize the unicyclic weighted digraphs with cycle weight r ∈ [-1, 1]\{0} having minimum and maximum iota energy. We obtain well known McClelland upper bound for the iota energy of weighted digraphs. Finally, we find the class of noncospectral equienergetic weighted digraphs. [ABSTRACT FROM AUTHOR]

Let D S be a weighted digraph of order n with a subdigraph S of order k , M ( D S ) its adjacency weight matrix and ρ ( D S ) its spectral radius. We consider the class C k of weighted digraphs of order k and we study the preorder in C k given by D S ′ ≾ D S if and only if ρ ( D S ′ ) ≤ ρ ( D S ) . We obtain that this order is equivalent to the entry-wise order M ( D S ′ ) ≤ M ( D S ) . Several points of view are taken, under varying regularity conditions, and k polynomial conditions for the comparison are presented. [ABSTRACT FROM AUTHOR]

This article deals with input-to-state stability (ISS) of discrete-time switched systems. Given a family of nonlinear systems with exogenous inputs, we present a class of switching signals under which the resulting switched system is ISS. We allow non-ISS systems in the family and our analysis involves graph-theoretic arguments. A weighted digraph is associated to the switched system, and a switching signal is expressed as an infinite walk on this digraph, both in a natural way. Our class of stabilizing switching signals (infinite walks) is periodic in nature and affords simple algorithmic construction. [ABSTRACT FROM AUTHOR]

Let G be a digraph and L G be its line digraph. Levine gave a formula that relates the number of rooted spanning trees of L G and that of G , with the restriction that G has no sources. In this note, we show that this restriction can be removed, thus his formula holds for all digraphs. [ABSTRACT FROM AUTHOR]

We study sequences of optimal walks of a growing length in weighted digraphs, or equivalently, sequences of entries of max-algebraic matrix powers with growing exponents. It is known that these sequences are eventually periodic when the digraphs are strongly connected. The transient of such periodicity depends, in general, both on the size of digraph and on the magnitude of the weights. In this paper, we show that some bounds on the indices of periodicity of (unweighted) digraphs, such as the bounds of Wielandt, Dulmage–Mendelsohn, Schwarz, Kim and Gregory–Kirkland–Pullman, apply to the weights of optimal walks when one of their ends is a critical node. [ABSTRACT FROM AUTHOR]

Abstract: Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs. [Copyright &y& Elsevier]

A weighted digraph is balanced if the sums of the weights of the incoming and of the outgoing edges are equal at each vertex. We show that if these sums are integers, then for any edge weights satisfying the balance conditions, there exist integer weights obtained by rounding the original weights up or down that preserve both the balance condition and the sum of all edge weights. [ABSTRACT FROM AUTHOR]