Search

The n -vertex graph G ( = Γ ( G ) ) with a non-singular real symmetric adjacency matrix G , having a zero diagonal and singular ( n − 1 ) × ( n − 1 ) principal submatrices is termed a NSSD, a Non-Singular graph with a Singular Deck. NSSDs arose in the study of the polynomial reconstruction problem and were later found to characterise non-singular molecular graphs that are distinct omni-conductors and ipso omni-insulators. Since both matrices G and G − 1 represent NSSDs Γ ( G ) and Γ ( G − 1 ) , the value of the nullity of a one-, two- and three-vertex deleted subgraph of G is shown to be determined by the corresponding subgraph in Γ ( G − 1 ) . Constructions of infinite subfamilies of non-NSSDs are presented. NSSDs with all two-vertex deleted subgraphs having a common value of the nullity are referred to as G -nutful graphs. We show that their minimum vertex degree is at least 4. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A, and let H(t)=exp(itA). For an eigenvalue μ of A with multiplicity k, a star set for μ in G is a vertex set X of G such that |X|=k and the induced subgraph G-X does not have μ as an eigenvalue. G is said to have perfect state transfer from the vertex u to the vertex v if there is a time τ such that |H(τ)u,v|=1. The unitary operator H(t) has important applications in the transfer of quantum information. In this paper, we give an expression of H(t). For a star set X of graph G, perfect state transfer does not occur between any two vertices in X. We also give some results for the existence of perfect state transfer in a graph. [ABSTRACT FROM AUTHOR]

We unify and generalize several inequalities for the number wk of walks of length k in graphs, and for the entry sum of matrix powers. First, we present a weighted sandwich theorem for Hermitian matrices which generalizes a matrix theorem by Marcus and Newman and which further generalizes our former unification of inequalities for the number of walks in undirected graphs by Lagarias et al. and by Dress and Gutman. The new inequality uses an arbitrary nonnegative weighting of the indices (vertices) which allows to apply the theorem to index (vertex) subsets (i.e., inequalities considering the number wk(S,S) of walks of length k that start at a vertex of a given vertex subset S and that end within the same subset). We also deduce a stronger variation of the sandwich theorem for the case of positive-semidefinite Hermitian matrices which generalizes another inequality of Marcus and Newman. Further, we show a similar theorem for nonnegative symmetric matrices which is another unification and generalization of inequalities for walk numbers by Erdős and Simonovits, by Dress and Gutman, and by Ilić and Stevanović. In the last part, we generalize lower bounds for the spectral radius of adjacency matrices and upper bounds for the energy of graphs. [ABSTRACT FROM AUTHOR]

Abstract: Let be a connected graph with vertex set and a weight function that assigns a nonnegative number to each of its vertices. Then, the -moment of at vertex is defined to be , where stands for the distance function. Adding up all these numbers, we obtain the -moment of : This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the Wiener index , when for every , and the degree distance , obtained when , the degree of vertex . In this paper we derive some exact formulas for computing the -moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding -moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same -moment for every (and hence with equal mean distance, Wiener index, degree distance, etc.). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product. [Copyright &y& Elsevier]

Abstract: A new operation on graphs is introduced and some of its properties are studied. We call it hierarchical product, because of the strong (connectedness) hierarchy of the vertices in the resulting graphs. In fact, the obtained graphs turn out to be subgraphs of the cartesian product of the corresponding factors. Some well-known properties of the cartesian product, such as reduced mean distance and diameter, simple routing algorithms and some optimal communication protocols are inherited by the hierarchical product. We also address the study of some algebraic properties of the hierarchical product of two or more graphs. In particular, the spectrum of the binary hypertree (which is the hierarchical product of several copies of the complete graph on two vertices) is fully characterized; turning out to be an interesting example of graph with all its eigenvalues distinct. Finally, some natural generalizations of the hierarchic product are proposed. [Copyright &y& Elsevier]

Abstract: The conditional diameter of a connected graph is defined as follows: given a property of a pair of subgraphs of , the so-called conditional diameter or -diameter measures the maximum distance among subgraphs satisfying . That is,In this paper we consider the conditional diameter in which requires that for all , for all , and for some integers and , where denotes the degree of a vertex x of , denotes the minimum degree and the maximum degree of . The conditional diameter obtained is called -diameter. We obtain upper bounds on the -diameter by using the k-alternating polynomials on the mesh of eigenvalues of an associated weighted graph. The method provides also bounds for other parameters such as vertex separators. [Copyright &y& Elsevier]

Let D be a digraph, and let Ln(D) and k(D) denote the nth iterated line digraph of D and the index of convergence of D, respectively. We prove that if D contains neither sources nor sinks, then: (1) k(Ln(D))=k(D)=0 if every connected component of D is a directed cycle. (2) k(Ln(D))=k(D)+n if there exists at least one connected component of D that is not a directed cycle. Finally, we prove that if D has no sources or no sinks then k(D)⩽k(L(D))⩽k(D)+1. [Copyright &y& Elsevier]