Search

In [1] , the set of refined inertias H n for sign patterns is expanded to H n ⁎ for zero-nonzero patterns. Also, it is proved that there are no zero-nonzero patterns of even order 2 m that require H 2 m ⁎ . In this paper, it is shown that there are no zero-nonzero patterns of odd order n ≥ 5 that require H n ⁎ , which together with the previous result prove that there are no zero-nonzero patterns of order n ≥ 4 that require H n ⁎ . [ABSTRACT FROM AUTHOR]

The trace norm of M ∈ M n ( C ) is defined as ‖ M ‖ ⁎ = ∑ k = 1 n σ k , where σ 1 ≥ σ 2 ≥ ⋯ ≥ σ n ≥ 0 are the singular values of M (i.e. the square roots of the eigenvalues of M M ⁎ ). We are particularly interested in the trace norm ‖ L ( D ) − a n I n ‖ ⁎ , where L ( D ) is the Laplacian matrix of a digraph D with n vertices and a arcs, and I n is the n × n identity matrix. When D = G is a graph with n vertices and m edges, then ‖ L ( D ) − a n I n ‖ ⁎ = ‖ L ( G ) − 2 m n I n ‖ ⁎ = L E ( G ) , the Laplacian energy of G introduced by Gutman and Zhou in 2006. We show that for a digraph D with n vertices and a arcs, ‖ L ( D ) − a n I n ‖ ⁎ ≤ n ( a − a 2 n + ∑ i = 1 n ( d i + ) 2 ) , where d 1 + , … , d n + are the outer degrees of the vertices of D . Moreover, the digraphs where this bound is attained are special classes of normally regular digraphs studied by Jørgensen in 2015 [6] . Finally, we construct normally regular digraphs where the equality is attained. [ABSTRACT FROM AUTHOR]

The energy E ( G ) of a graph G is the sum of the absolute values of all eigenvalues of G . We are interested in the relation between the energy of a graph G and the matching number μ ( G ) of G . It is proved that E ( G ) ≥ 2 μ ( G ) for every graph G , and E ( G ) ≥ 2 μ ( G ) + 5 5 c 1 ( G ) if the cycles of G (if any) are pairwise vertex-disjoint, where c 1 ( G ) denotes the number of odd cycles in G . Besides, we prove that E ( G ) ≥ r ( G ) + 1 2 if G has at least one odd cycle and it is not of full rank, where r ( G ) is the rank of G . [ABSTRACT FROM AUTHOR]

Let M be a real square matrix. We give upper bounds for the sum of the absolute values of the (real part of the) eigenvalues of M , quantity in some particular cases known as (real) energy of M . From these results we obtain a combinatorial bound for the real energy of the Coxeter matrix Φ Q of a tree digraph Q with n vertices, e r e ( Φ Q ) ≤ min n ( 2 a + b + c + d ) 2 , where a is the number of edges, b and c are respectively the number of bifurcation and congregation paths of Q (as defined below), d = ∑ i = 1 n [ δ ( i ) − 1 ] [ δ ( i ) − 2 ] with δ ( i ) the degree of a vertex i , and where the minimum is taken over all possible orientations of edges in Q . As particular case we consider Dynkin, Euclidean and star graphs, obtaining practical bounds for the real Coxeter energy of these classes of digraphs. [ABSTRACT FROM AUTHOR]

We first prove a few simple results to illustrate some algebraic combinatorial features of the q -permanent. This is followed by a characterization of a noncrossing permutation in terms of the numbers of inversions of its cycles. Then we use a family of derivative formulas for the q -permanent of a square matrix A to characterize several structures of noncrossing kind. Each such formula f characterizes a set D f of digraphs, in the sense that D ∈ D f iff f is valid for all matrices A with digraph D . In this way we characterize, among others, digraphs with noncrossing permutation subdigraphs, noncrossing graphs, noncrossing forests. We use the derivative formulas to prove two particular cases of a conjecture on the q -monotonicity of the q -permanent of a Hermitian positive definite matrix. [ABSTRACT FROM AUTHOR]

In this article, we focus on structural properties of minimal strong digraphs (MSDs). We carry out a comparative study of properties of MSDs versus (undirected) trees. For some of these properties, we give the matrix version, regarding nearly reducible matrices. We give bounds for the coefficients of the characteristic polynomial corresponding to the adjacency matrix of trees, and we conjecture bounds for MSDs. We also propose two different representations of an MSD in terms of trees (the union of a spanning tree and a directed forest; and a double directed tree whose vertices are given by the contraction of connected Hasse diagrams). [ABSTRACT FROM AUTHOR]

In this paper we determine the tropical algebraic eigenvalues of Toeplitz matrices. It is proved that these matrices have at most two distinct tropical eigenvalues and the explicit formulas for those eigenvalues are given. Also, the asymptotic behavior of eigenvalues of parameterized tridiagonal Toeplitz matrices over the classical field of complex numbers is shown. [ABSTRACT FROM AUTHOR]

The notions of weakly bipartitive and bipartitive families were introduced by Montgolfier (2003) as a general tool for studying some decomposition of graphs and other combinatorial structures. One way to construct such families comes from a result of Loewy (1986): Given an irreducible n × n matrix A over a field, the family of partitions { X , Y } of { 1 , … , n } such that the submatrices A [ X , Y ] and A [ Y , X ] have a rank at most 1 is weakly bipartitive. In this paper, we show that this family is bipartitive when A is symmetric. In the converse direction, we prove that weakly bipartitive and bipartitive families are all obtained via the construction above. [ABSTRACT FROM AUTHOR]

Let M n ( C ) denote the space of n × n matrices with entries in C . We define the energy of A ∈ M n ( C ) as (1) E ( A ) = ∑ k = 1 n | λ k − t r ( A ) n | where λ 1 , … , λ n are the eigenvalues of A, tr ( A ) is the trace of A and | z | denotes the modulus of z ∈ C . If A is the adjacency matrix of a graph G then E ( A ) is precisely the energy of the graph G introduced by Gutman in 1978. In this paper, we compare the energy E with other well-known energies defined over matrices. Then we find upper and lower bounds of E which extend well-known results for the energies of graphs and digraphs. Also, we obtain new results on energies defined over the adjacency, Laplacian and signless Laplacian matrices of digraphs. [ABSTRACT FROM AUTHOR]

Kautz digraphs K ( d , ℓ ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz C K ( d , ℓ ) and the subKautz s K ( d , 2 ) digraphs were recently introduced by Böhmová, Huemer and the author. In this paper we propose a new method to obtain the complete spectra of subKautz s K ( d , 2 ) and cyclic Kautz C K ( d , 3 ) digraphs, for all d ≥ 3 , through the Hoffman–McAndrew polynomial and regular partitions. This approach can be useful to find the spectra of other families of digraphs with high regularity. [ABSTRACT FROM AUTHOR]

This note corrects an error in the results of Subsection 3.1 in authors' paper “On Eigenvalues of Laplacian Matrix for a Class of Directed Signed Graphs”, which appeared in Linear Algebra and its Applications 523 (2017), 281–306. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected graph and G σ the corresponding oriented graph of G with the orientation σ . The skew energy of G σ , denoted by ε ( G σ ) , is defined as the sum of the singular values of its skew adjacency matrix S ( G σ ) . In 2010, Adiga et al. proved ε ( G σ ) ≤ n Δ , where Δ is the maximum degree of G of order n . In this paper, we characterize the skew energy of a tournament and present some properties about an optimum skew energy tournament. [ABSTRACT FROM AUTHOR]

In this paper, we consider upper bounds on the size of transitive subtournaments in a digraph. In particular, we give an upper bound based on linear algebraic techniques similarly to Hoffman's bound for the size of cocliques in a regular graph. Furthermore, we partially improve the bound for doubly regular tournaments by using the technique of Greaves and Soicher for strongly regular graphs [4] , which gives a new application of block intersection polynomials. [ABSTRACT FROM AUTHOR]

We show that the line digraph technique, when iterated, provides dense digraphs, that is, with asymptotically large order for a given diameter (or with small diameter for a given order). This is a well-known result for regular digraphs. In this note we prove that this is also true for non-regular digraphs. [ABSTRACT FROM AUTHOR]

Let G be a simple graph, and let G σ be an oriented graph of G with skew adjacency matrix S ( G σ ) . The skew spectral radius ρ s ( G σ ) of G σ is defined as the spectral radius of S ( G σ ) . When G is an odd-cycle graph (no even cycle), Cavers et al. (2012) [4] showed that the skew spectral radius of G σ is the same for every orientation σ of G . They proposed a problem: If G is a connected graph and ρ s ( G σ ) is the same for all orientations σ of G , must G be an odd-cycle graph? In this paper, we solve this problem and give a positive answer. [ABSTRACT FROM AUTHOR]

The eigenvalues of the Laplacian matrix for a class of directed graphs with both positive and negative weights are studied. The Laplacian matrix naturally arises in a wide range of applications involving networks. First, a class of directed signed graphs is studied in which one pair of nodes (either connected or not) is perturbed with negative weights. A necessary and sufficient condition is proposed to attain the following objective for the perturbed graph: the real parts of the non-zero eigenvalues of its Laplacian matrix are positive. Under certain assumption on the unperturbed graph, it is established that the objective is achieved if and only if the magnitudes of the added negative weights are smaller than an easily computable upper bound. This upper bound is shown to depend on the topology of the unperturbed graph. It is also pointed out that the obtained condition can be applied in a recursive manner to deal with multiple edges with negative weights. Secondly, for directed graphs, a subset of pairs of nodes are identified where if any of the pairs is connected by an edge with infinitesimal negative weight, the resulting Laplacian matrix will have at least one eigenvalue with negative real part. Illustrative examples are presented to show the applicability of our results. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected graph and G σ be the corresponding oriented graph of G with the orientation σ . The skew energy of G σ , denoted by ε s ( G σ ), is defined as the sum of the singular values of the skew adjacency matrix S ( G σ ). In 2010, Adiga et al. certified that ɛ s ( G σ ) ≤ n Δ , where Δ is the maximum degree of G of order n . It has been shown that every 5-regular oriented graph with optimum skew energy has even neighborhood property, that is each pair of neighborhoods of a graph have even number of common vertices. In this paper, we characterize all connected 5-regular graphs of order n with this property. Moreover, we determine all connected 5-regular oriented graphs of order n with maximum skew-energy. [ABSTRACT FROM AUTHOR]

The energy E ( G ) of a graph G is the sum of the absolute values of all eigenvalues of G . In this paper, we give a lower bound and an upper bound for graph energy in terms of vertex cover number. For a graph G with vertex cover number τ , it is proved that 2 τ − 2 c ≤ E ( G ) ≤ 2 τ Δ , where c is the number of odd cycles in G and Δ is the maximum vertex degree of G . The lower bound is attained if and only if G is the disjoint union of some complete bipartite graphs with perfect matchings and some isolated vertices, the upper bound is attained if and only if G is the disjoint union of τ copies of K 1 , Δ together with some isolated vertices. [ABSTRACT FROM AUTHOR]

Let G be a graph. An edge orientation of G is called smooth if the in-degree and the out-degree of every vertex differ by at most one. In this paper, we show that if G is a 2-edge-connected non-bipartite graph with δ ( G ) ≥ 3 , then G has a smooth primitive orientation. Among other results, using the spectral radius of digraphs, we show that if D 1 is a primitive regular orientation and D 2 is a non-regular orientation of a given graph, then for sufficiently large t , the number of closed walks of length t in D 1 is more than the number of closed walks of length t in D 2 . [ABSTRACT FROM AUTHOR]

A set H n ⁎ of refined inertias for zero–nonzero patterns is introduced that is analogous to the set H n previously considered for sign patterns. For n = 3 and 4, a complete characterization of irreducible zero–nonzero patterns that allow or require H n ⁎ is given, and each zero–nonzero pattern that allows H n ⁎ has a signing that allows H n . In contrast, for n ≥ 5 a family of irreducible zero–nonzero patterns is given that allows H n ⁎ but for which no one signing allows H n . [ABSTRACT FROM AUTHOR]

We introduce the concept of general complex weighted directed graphs where each edge is assigned a complex number. Necessary and sufficient conditions for the Laplacian matrix to be singular/nonsingular are derived. Our results give the relationship between the Laplacian matrix and the structure of its corresponding directed graph. Compared with the existing results, our main contribution is that our results are established without the restriction that the adjacency matrix is Hermitian. [ABSTRACT FROM AUTHOR]

We study isospectrality for mixed Dirichlet–Neumann boundary conditions and extend the previously derived graph-theoretic formulation of the transplantation method. Led by the theory of Brownian motion, we introduce vertex-colored and edge-colored line graphs that give rise to block diagonal transplantation matrices. In particular, we rephrase the transplantation method in terms of representations of free semigroups and provide a method for generating adjacency cospectral weighted directed graphs. [ABSTRACT FROM AUTHOR]

We study the concept of the Coxeter energy of graphs and digraphs (quivers) as an analogue of Gutman's adjacency energy, which has applications in theoretical chemistry and is a recently widely investigated graph invariant. Coxeter energy CE ( G ) of a (di)graph G is defined to be the sum of the absolute values of all complex eigenvalues of the Coxeter matrix associated with G . Our main inspiration for the study comes from the Coxeter formalism appearing in group theory, Lie theory, representation theory of algebras, mathematical physics and other contexts. We focus on the Coxeter energy of trees and we prove that the path (resp. the maximal star) has the smallest (resp. the greatest) Coxeter energy among all trees (resp. two large subclasses of trees) with fixed number of vertices. We provide several other related results, as the characterization of trees with second smallest and second greatest Coxeter energy, bounds for Coxeter energy, and general facts on Coxeter spectra of graphs extending known results e.g. for Salem trees and for certain special real Coxeter eigenvalues of trees. Additionally, we discuss few other energy-like quantities for the Coxeter spectra of (di)graphs, including Coxeter energy “normalized” by the trace of the Coxeter matrix and the quantities derived from variants of Coulson integral formula. [ABSTRACT FROM AUTHOR]

This paper is about the combinatorics of finite point configurations in the tropical projective space or, dually, of arrangements of finitely many tropical hyperplanes. Moreover, arrangements of finitely many tropical halfspaces can be considered via coarsenings of the resulting polyhedral decompositions of R d . This leads to natural cell decompositions of the tropical projective space TP min d − 1 . Our method is to employ a known class of ordinary convex polyhedra naturally associated with weighted digraphs. This way we can relate to and use results from combinatorics and optimization. One outcome is the solution of a conjecture of Develin and Yu (2007). [ABSTRACT FROM AUTHOR]

Ordering of the oriented unicyclic graphs with n vertices according to their minimal skew energies is investigated. We derive the first 22 oriented unicyclic graphs for n ≥ 1784 and a series of oriented unicyclic graphs for 3 ≤ n ≤ 1783. [ABSTRACT FROM AUTHOR]

A digraph Γ = ( V , E ) is a line digraph when every pair of vertices u , v ∈ V have either equal or disjoint in-neighborhoods. When this condition only applies for vertices in a given subset (with at least two elements), we say that Γ is a locally line digraph. In this paper we give a new method to obtain a digraph Γ ′ cospectral with a given locally line digraph Γ with diameter D , where the diameter D ′ of Γ ′ is in the interval [ D − 1 , D + 1 ] . In particular, when the method is applied to De Bruijn or Kautz digraphs, we obtain cospectral digraphs with the same algebraic properties that characterize the formers. [ABSTRACT FROM AUTHOR]

Denote the scrambling index set of primitive minimally strong digraphs of order n by SI n . For n ≥ 13 , we show that SI n contains all integers in the interval [ 3 , K 1 ( n ) ] , where K 1 ( n ) = { n 2 + 12 n − 13 8 , if both n and n + 1 2 are odd , n 2 + 12 n − 5 8 , if n is odd and n + 1 2 is even , n 2 + 10 n − 16 8 , if n is even and n 2 is odd , n 2 + 10 n − 8 8 , if both n and n 2 are even . We also identify all elements of SI n which are larger than ( n 2 − 6 n + 13 ) / 2 ( n is odd) or ( n 2 − 6 n + 12 ) / 2 ( n is even). It is shown that there exist more “gaps” in the set SI n . [ABSTRACT FROM AUTHOR]

The n × n matrix A is integrally normalizable with respect to a prescribed subset M of { ( i , j ) : i , j = 1 , 2 , … , n and i ≠ j } provided A is diagonally similar to an integer matrix each of whose entries in positions corresponding to M is equal to 1. In the case that the elements of M form the arc set of a spanning tree, the matrices that are integrally normalizable with respect to M have been characterized. This paper gives a characterization for general subsets M . In addition, necessary and sufficient conditions for each matrix with a given zero–nonzero pattern to be integrally normalizable with respect to an arbitrary subset M are given. [ABSTRACT FROM AUTHOR]

By the square root of a (square) matrix A we mean a matrix B that satisfies B 2 = A . In this paper, we begin a study of the (entrywise) nonnegative square roots of nonnegative matrices, adopting mainly a graph-theoretic approach. To start with, we settle completely the question of existence and uniqueness of nonnegative square roots for 2-by-2 nonnegative matrices. By the square of a digraph H , denoted by H 2 , we mean the digraph with the same vertex set as H such that ( i , j ) is an arc if there is a vertex k such that ( i , k ) and ( k , j ) are both arcs in H . We call a digraph H a square root of a digraph G if H 2 = G . It is observed that a necessary condition for a nonnegative matrix to have a nonnegative square root is that its digraph has a square root, and also that a digraph G has a square root if and only if there exists a nonnegative matrix A with digraph G such that A has a nonnegative square root. We consider when or whether certain kinds of digraphs (including digraphs that are disjoint union of directed paths and circuits, permutation digraphs or a special kind of bigraphs) have square roots. We also consider when certain kinds of nonnegative matrices (including monomial matrices, rank-one matrices and nilpotent matrices with index two) have nonnegative square roots. A known characterization of loopless digraphs to have square roots, due to F. Escalantge, L. Montejano, and T. Rojano, is extended (and amended) to digraphs possibly with loops. Some natural open questions are also posed. [ABSTRACT FROM AUTHOR]

Matrices A of order n having entries in the field F ( x 1 , … , x n ) of rational functions over a field F and characteristic polynomial det ⁡ ( t I − A ) = t n + x 1 t n − 1 + ⋯ + x n − 1 t + x n are studied. It is known that such matrices are irreducible and have at least 2 n − 1 nonzero entries. Such matrices with exactly 2 n − 1 nonzero entries are called Ma–Zhan matrices. Conditions are given that imply that a Ma–Zhan matrix is similar via a monomial matrix to a generalized companion matrix (that is, a lower Hessenberg matrix with ones on its superdiagonal, and exactly one nonzero entry in each of its subdiagonals). Via the Ax–Grothendieck Theorem (respectively, its analog for the reals) these conditions are shown to hold for a family of matrices whose entries are complex (respectively, real) polynomials. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected graph, and G ϕ be a mixed graph of G with the generalized orientation ϕ and Hermitian-adjacency matrix H ( G ϕ ) . Then G is called the underlying graph of G ϕ . The Hermitian energy of the mixed graph G ϕ , denoted by E H ( G ϕ ) , is defined as the sum of all the singular values of H ( G ϕ ) . A k -regular mixed graph on n vertices having Hermitian energy n k is called a k -regular optimum Hermitian energy mixed graph. Liu and Li (2015) [11] proposed the problem of determining all the k -regular connected optimum Hermitian energy mixed graphs. This paper is to give a solution to the problem for the case k = 3 . [ABSTRACT FROM AUTHOR]

An oriented graph G σ is a digraph without loops and multiple arcs, where G is called the underlying graph of G σ . Let S ( G σ ) denote the skew-adjacency matrix of G σ . The rank of S ( G σ ) is called the skew-rank of G σ , denoted by sr ( G σ ) , which is even since S ( G σ ) is skew symmetric. Li and Yu (2015) [12] proved that the skew-rank of an oriented unicyclic graph G σ is either 2 m ( G ) − 2 or 2 m ( G ) , where m ( G ) denotes the matching number of G . In this paper, we extend this result to general cases. It is proved that the skew-rank of an oriented connected graph G σ is an even integer satisfying 2 m ( G ) − 2 β ( G ) ≤ sr ( G σ ) ≤ 2 m ( G ) , where β ( G ) = | E ( G ) | − | V ( G ) | + 1 is the number of fundamental cycles (also called the first Betti number). Besides, the oriented graphs satisfying sr ( G σ ) = 2 m ( G ) − 2 β ( G ) are characterized definitely. [ABSTRACT FROM AUTHOR]

Let D be a primitive digraph of order n and 1 ≤ m ≤ n . The m -competition index of D is the smallest positive integer k such that every pair of vertices x and y of D have at least m common preys in D k . In this paper, the upper bound of m -competition indices ( 1 ≤ m ≤ n − 1 ) for primitive minimally strong digraphs of order n is obtained. Furthermore, it is shown that for 1 ≤ m ≤ n − 1 , there exist “gaps” in the m -competition index set of primitive minimally strong digraphs of order n . [ABSTRACT FROM AUTHOR]

Let G σ be an oriented graph and S ( G σ ) be its skew-adjacency matrix. The skew-rank of G σ , denoted by sr ( G σ ), is the rank of S ( G σ ). In this paper, we characterize all the bicyclic oriented graphs with skew-rank 6. Let G σ be a bicyclic oriented graph with pendant vertices but no pendant twins. If s r ( G σ ) = 6 , then 6 ≤ | V ( G σ )| ≤ 10. [ABSTRACT FROM AUTHOR]

We explore the spectral properties of digraph Laplacians and how they relate to topological properties of digraphs (such as openness, closure, and strong connectedness) under the Alexandrov topology. [ABSTRACT FROM AUTHOR]

Let G be a graph with maximum degree Δ, and let G σ be an oriented graph of G with skew adjacency matrix S ( G σ ) . The skew spectral radius ρ s ( G σ ) of G σ is defined as the spectral radius of S ( G σ ) . The skew spectral radius has been studied, but only few results about its lower bound are known. This paper determines some lower bounds of the skew spectral radius, and then studies the oriented graphs whose skew spectral radii attain the lower bound Δ . Moreover, we apply the skew spectral radius to the skew energy of oriented graphs, which is defined as the sum of the norms of all the eigenvalues of S ( G σ ) , and denoted by E s ( G σ ) . As a result, we obtain some lower bounds of the skew energy, which improve the known lower bound obtained by Adiga et al. [ABSTRACT FROM AUTHOR]

Let T be an (abstract) set of types , and let ι , o : T → Z + . A T - diagram is a locally ordered directed graph G equipped with a function τ : V ( G ) → T such that each vertex v of G has indegree ι ( τ ( v ) ) and outdegree o ( τ ( v ) ) . (A directed graph is locally ordered if at each vertex v , linear orders of the edges entering v and of the edges leaving v are specified.) Let V be a finite-dimensional F -linear space, where F is an algebraically closed field of characteristic 0. A function R on T assigning to each t ∈ T a tensor R ( t ) ∈ V ⁎ ⊗ ι ( t ) ⊗ V ⊗ o ( t ) is called a tensor representation of T . The trace (or partition function ) of R is the F -valued function p R on the collection of T -diagrams obtained by ‘decorating’ each vertex v of a T -diagram G with the tensor R ( τ ( v ) ) , and contracting tensors along each edge of G , while respecting the order of the edges entering v and leaving v . In this way we obtain a tensor network . We characterize which functions on T -diagrams are traces, and show that each trace comes from a unique ‘strongly nondegenerate’ tensor representation. The theorem applies to virtual knot diagrams, chord diagrams, and group representations. [ABSTRACT FROM AUTHOR]

For a positive integer m , the m -competition graph of an irreducible Boolean matrix A of order n , denoted by C m ( A ) , is the graph that has the same vertex set as its digraph D ( A ) , and there is an edge between vertices x and y ( x ≠ y ) if and only if there exist m distinct vertices v 1 , v 2 , ⋯ , v m such that x → v i and y → v i for 1 ≤ i ≤ m in D . The smallest positive integer q such that C m ( A q + i ) = C m ( A q + r + i ) for some positive integer r and every nonnegative integer i is called the m -competition index (generalized competition index) of A . In this paper, we characterize irreducible Boolean matrices with the largest generalized competition index. [ABSTRACT FROM AUTHOR]

Serial quasi-compact T 1 -spaces are exactly the spaces that arise as maximal spectra of Bézout domains. The closed unit interval is serial. A nested sequence of directed graphs is constructed to show that the unit square is still serial. Using arguments of combinatorial set theory, it is proved that big powers of the unit interval are not serial. [ABSTRACT FROM AUTHOR]

Let G σ be an oriented graph and P s ( G σ ; x ) = det ( x I − S ( G σ ) ) be the skew-characteristic polynomial of its skew-adjacency matrix S ( G σ ) . The skew-energy of G σ is defined to be the sum of the absolute values of eigenvalues of S ( G σ ) . In this paper, we firstly find a novel relation between the coefficients of skew-characteristic polynomial of unicyclic graph with the third largest skew-energy and bicyclic oriented graphs, and then use it along with other techniques to characterize the bicyclic oriented graphs with the second largest skew-energy. [ABSTRACT FROM AUTHOR]

Abstract: An equivalent of kernel existence is formulated using semikernels. It facilitates inductive arguments, which allow us to establish several sufficient conditions for the existence of kernels in finite digraphs. The conditions identify classes of digraphs that have kernels without necessarily being kernel perfect. [Copyright &y& Elsevier]

Abstract: In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamiltonian graph. Hendry’s conjecture in this case is that every principle submatrix of A that dominates a full cycle permutation matrix is a principle submatrix of a principle submatrix of A that dominates a full cycle permutation matrix. This article generalizes the concept of cycle-extendability to S-extendable; that is, with and G a graph on n vertices, G is S-extendable if the vertices of every non-Hamiltonian cycle are contained in a cycle length i greater, where . We investigate this concept in directed graphs and in particular tournaments, i.e., anti-symmetric matrices with zero main diagonal. [Copyright &y& Elsevier]

Abstract: The concept of returnability is proposed for complex directed networks (digraphs). It can be seen as a generalization of the concept of reciprocity. Two measures of the returnability are introduced. We establish closed formulas for the calculation of the returnability measures, which are also related to the digraph spectrum. The two measures are calculated for simple examples of digraphs as well as for real-world complex directed networks and are compared with the reciprocity. [Copyright &y& Elsevier]

Motivated by a problem on message routing in communication networks, Graham and Pollak proposed a scheme for addressing the vertices of a graph G by N-tuples of three symbols in such a way that distances between vertices may readily be determined from their addresses. They observed that N ≥ h(D), the maximum of the number of positive and the number of negative eigenvalues of the distance matrix D of G. A result of Gregory, Shader and Watts yields a necessary condition for equality to occur. As an illustration, we show that N >h(D) = 5 for all addressings of the Petersen graph and then give an optimal addressing by 6-tuples. [Copyright &y& Elsevier]