Search

A combinatorial approach is given to compute bases for eigenspaces of zero-divisor graphs of finite Boolean rings. A commutative monoid $ \mathcal {S} $ S of graphs is shown to contain a cyclic submonoid $ \mathcal {U} $ U that determines values of the entries of basis elements, while the members of its complement $ \mathcal {S}\setminus \mathcal {U} $ S ∖ U encode the supports of these elements. Furthermore, every member of $ \mathcal {S}\setminus \mathcal {U} $ S ∖ U is associated with a Catalan-triangle number, which counts the number of basis elements whose supports are determined by the given member. This is established by using a combinatorial interpretation of Catalan-triangle numbers to produce linearly independent sets of eigenvectors. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with adjacency matrix $ A(G) $ A (G) and distance matrix $ \mathcal {D}(G) $ D (G). The adjacency-distance matrix of G is defined as $ S(G) = \mathcal {D}(G) + A(G) $ S (G) = D (G) + A (G). In this paper, $ S(G) $ S (G) is generalized by the convex linear combinations \[ S_{\alpha}(G)=\alpha \mathcal{D}(G)+(1-\alpha)A(G) \] S α (G) = α D (G) + (1 − α) A (G) where $ \alpha \in [0,1] $ α ∈ [ 0 , 1 ]. Let $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) be the spectral radius of $ S_{\alpha }(G) $ S α (G). This paper presents results on $ S_{\alpha }(G) $ S α (G) with emphasis on $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) and some results on $ S(G) $ S (G) are extended to all α in some subintervals of $ [0,1] $ [ 0 , 1 ]. For $ \alpha \in [1/2,1] $ α ∈ [ 1 / 2 , 1 ] , the trees attaining the largest and the smallest $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) among trees of fixed order are determined and it is proved that $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) is a branching index. Moreover, for $ \alpha \in (1/2,1] $ α ∈ (1 / 2 , 1 ] , the graphs that uniquely minimize $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) : among all connected graphs of fixed order and fixed connectivity, and among all connected graphs of fixed order and fixed chromatic number are characterized. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix $ A(G) $ A (G). Let $ \tau (G) $ τ (G) denote the smallest positive eigenvalue of $ A(G) $ A (G). In 1990, Pavlíková and Kr $ \breve{c} $ c ˘ -Jediný proved that among all nonsingular trees on n = 2m vertices, the comb graph (obtained by taking a path on m vertices and adding a new pendant vertex to every vertex of the path) has the maximum τ value. We consider the problem for unicyclic graphs. Let $ \mathscr {U} $ U denote the class of all connected bipartite unicyclic graphs with a unique perfect matching, and for each $ m\geq ~3 $ m ≥ 3 , let $ \mathscr {U}_n $ U n be the subclass of $ \mathscr {U} $ U with graphs on n = 2m vertices. We first obtain the classes of unicyclic graphs U in $ \mathscr {U} $ U such that $ \tau (U)\leq \sqrt {2}-1 $ τ (U) ≤ 2 − 1. We then find the unique graph $ U_o^n $ U o n (resp. $ U_e^n $ U e n ) having the maximum τ value among all graphs in $ \mathscr {U}_n $ U n when m is odd (resp. when m is even). Finally, we prove that $ U_o^6 $ U o 6 (the graph obtained from a cycle of order 4, by adding two pendants to two adjacent vertices) is the graph with maximum τ value among all graphs in $ \mathscr {U} $ U . As a consequence, we obtain a sharp upper bound for $ \tau (U) $ τ (U) when $ U\in \mathscr {U} $ U ∈ U . [ABSTRACT FROM AUTHOR]

Let G be a graph, and let $ A(G) $ A (G) be the adjacency matrix of G. The computation of permanent of $ A(G) $ A (G) is #p-complete. Computing permanent of $ A(G) $ A (G) is of great interest in quantum chemistry, statistical physics, among other disciplines. In this paper, we characterize the ordering of permanents of adjacency matrices of all graphs obtained from regular complete bipartite graph $ K_{p, p} $ K p , p by deleting six edges. As an application, we show that all graphs with a perfect matching obtained from $ K_{p, p} $ K p , p with six edges deleted are determined by their permanental polynomials. [ABSTRACT FROM AUTHOR]

We consider particular weighted directed graphs with edges having colour red, blue or green such that each red edge has weight 1, each blue edge has weight $ -1 $ − 1 and each green edge has weight $ \mathrm {i} $ i (the imaginary unit). Such a directed graph is called a 3-coloured digraph (for short, a 3-CD). Every mixed graph and every signed graph can be interpreted as a 3-CD. We first study some structural properties of 3-CDs by means of the eigenvalues of the adjacency matrix. In particular, we give spectral criteria for singularity of such digraphs. Second, we consider weight-symmetric 3-CDs, i.e. those 3-CDs that are switching isomorphic to their negation. It follows that the class of weight-symmetric 3-CDs is included in the class of 3-CDs whose spectrum is symmetric (with respect to the origin). We give some basic properties and several constructions of weight-symmetric 3-CDs and establish constructions of 3-CDs which have symmetric spectrum but are not weight-symmetric. [ABSTRACT FROM AUTHOR]

For a simple graph G, the ABC-index is a degree based topological index and is defined as where dv is the degree of the vertex υ in G. Recently, the Laplacian ABC-matrix was introduced in [22] is defined by where is the diagonal matrix of ABC-degrees and Ã(G) is the ABC-matrix of G: The eigenvalues of the matrix are called the Laplacian ABC-eigenvalues of G. In the article, we consider the problem of characterization of connected graphs having exactly three distinct Laplacian ABC-eigenvalues. We solve this problem for bipartite graphs, multipartite graphs, unicyclic graphs, regular graphs and prove the non-existence of such graphs with diameter greater than 2. We introduce the concept of trace norm of the matrix called the Laplacian ABC-energy of G. We obtain some upper and lower bounds for the Laplacian ABC-energy and characterize the extremal graphs which attain these bounds. [ABSTRACT FROM AUTHOR]

Let G n , β be the set of graphs of order n with given matching number β. Let D (G) be the diagonal matrix of the degrees of the graph G and A (G) be the adjacency matrix of the graph G. The largest eigenvalue of the nonnegative matrix A α (G) = α D (G) + A (G) is called the α-spectral radius of G. The graphs with maximal α-spectral radius in G n , β are completely characterized in this paper. In this way, we provide a general framework to attack the problem of extremal spectral radius in G n , β . More precisely, we generalize the known results on the maximal adjacency spectral radius in G n , β and the signless Laplacian spectral radius. [ABSTRACT FROM AUTHOR]

With the makespan as the optimisation goal, we propose a hybrid solving method that combines improved extended shifting bottleneck procedure (i-ESB) and genetic algorithm (GA) for the assembly job shop scheduling problem (AJSSP). Hybrid genetic algorithm (HGA) uses a GA based on operation constraint chain coding to achieve global search and a local search based on an i-ESB. In the design of i-ESB, an extended disjunctive graph model (EDG) corresponding to AJSSP is presented. The calculation method of the operation head and tail length based on EDG is studied, as well as the searching method of key operations. The Schrage algorithm with disturbance is used to solve the single-machine scheduling subproblem. The selection criterion for bottleneck machines is increased. A greedy bottleneck machine re-optimisation process is designed. The effectiveness and superiority of the proposed algorithm are verified by testing and analysing the relevant examples in the literature. [ABSTRACT FROM AUTHOR]

The class of unicyclic non-bipartite graphs with unique perfect matching, denoted by U , is considered in this article. This article provides a complete characterization of unicyclic graphs in U which possess tricyclic inverses. [ABSTRACT FROM AUTHOR]

It was shown in 2006 that among the nonsingular trees T (whose adjacency matrix A(T) is nonsingular), the corona trees (trees that are obtained by taking any tree T and then adding a new pendant vertex at each vertex of T) are the only ones which satisfy the reciprocal eigenvalue property (λ is an eigenvalue of A(T) if and only if 1 λ is an eigenvalue of A(T), where their multiplicities are allowed to be different). A general question remained open. Can there be a tree which has at least one zero eigenvalue and whose nonzero eigenvalues satisfy the reciprocal eigenvalue property? In this note, we show that there are no such trees with at least two vertices. The proof is a beautiful application of the product of graphs. [ABSTRACT FROM AUTHOR]

The energy of a graph is defined as the sum of the absolute values of all eigenvalues with respect to its adjacency matrix. Denote by Gn,m the set of all connected graphs having n vertices and m edges. Caporossi et al. [Caporossi G, Cvetkovi D, Gutman I, et al. Variable neighbourhood search for extremal graphs. 2. Finding graphs with external energy. J Chem Inf Comput Sci. 1999;39:984–996] conjectured that among all graphs in Gn,m, n ≥ 6 and n − 1 ≤ m ≤ 2(n − 2), the graphs with minimum energy are the star Sn with m−n + 1 additional edges all connected to the same vertices for m ≤ n + ⌊ (n − 7) / 2 ⌋ , and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. In this paper, we provide a new approach to investigate the conjecture above. Especially, we determine the unique tetracyclic graph having minimum energy. [ABSTRACT FROM AUTHOR]

This article provides a combinatorial description of the inverse of the adjacency matrix of a non-singular 3-coloured digraph. The class of unicyclic 3-coloured digraphs with the cycle weight ±i and with a unique perfect matching, denoted by U g , is considered in this article. We characterize the 3-coloured digraphs in U g whose inverses are again 3-coloured digraphs. Furthermore, the 3-coloured digraphs in U g whose inverses are bipartite are also characterized. It is proved that the inverses of the 3-coloured digraphs in U g are always Laplacian non-singular. Characterizations of unicyclic 3-coloured digraphs in U g possessing unicyclic inverses are also supplied in this article. As an application, we can obtain the class of unicyclic 3-coloured digraphs with the cycle weight ±i satisfying the strong reciprocal eigenvalue property. [ABSTRACT FROM AUTHOR]

The use of an appropriate design is a very important aspect of agroforestry experimentation. Since different species of trees may interact spatially, plots in agroforestry could be connected through network of trees which would create non-directional adjacency effects on a plot. Hence, there is a need to take the "direct effect of trees" and "tree network effects" on the crop into account when designing an agroforestry experiment. Tree network effect refers to the influence a tree exerts on the surrounding plots as a result of adjacency of the plots. In this paper, a class of network designs incorporating effects of trees from adjacent plots has been obtained. The characterization properties of the designs have also been studied. The designs are found to be variance balanced for the estimation of direct as well as network effects of trees. They are also highly efficient designs, and hence, are recommended for agroforestry experimentation with multiple tree species and a single crop. [ABSTRACT FROM AUTHOR]

Let G be an undirected graph with adjacency matrix A (G). For a vertex u ∈ V (G) , the subgraph centrality of u in G is C S (u) = (exp ⁡ (A (G))) u u = ∑ k = 0 ∞ 1 k ! (A (G) k) u u . In this paper, we give some formulas for C S (u) by using equitable partitions and star sets of G. [ABSTRACT FROM AUTHOR]

In [A note about cospectral graphs for the adjacency and normalized Laplacian matrices. Linear Multilinear Algebra. 2010;58(3-4):387–390], Butler constructed a family of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. In this article, we extend this construction for generating larger classes of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. Also, we provide a couple of constructions of non-bipartite graphs, which are cospectral for the adjacency matrices but not necessarily for the normalized Laplacian matrices. [ABSTRACT FROM AUTHOR]

The class of non-bipartite unicyclic graphs with a unique perfect matching, denoted by U , is considered in this article. This article describes the entries of the inverse of the adjacency matrix of a graph in U . It is proved that the inverse graph of a graph in U is always non-bipartite. In this article, we characterize the graphs in U whose inverses are mixed graphs. Among all such graphs in U we identify those graphs whose inverses are quasi-bipartite. Furthermore, characterizations of unicyclic graphs in U possessing unicyclic and bicyclic inverses are also provided in this article. [ABSTRACT FROM AUTHOR]

Let G be a digraph and A (G) be the adjacency matrix of G. Let D (G) be the diagonal matrix with outdegrees of vertices of G. For any real α ∈ [ 0 , 1 ] , define the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G). The largest modulus of the eigenvalues of A α (G) is called the A α spectral radius of G. In this paper, we determine the digraphs which attain the maximum (or minimum) A α spectral radius among all strongly connected digraphs with given parameters such as girth, clique number, vertex connectivity or arc connectivity. We also propose an open problem. [ABSTRACT FROM AUTHOR]

Given two graphs, a backbone and a finger, a comb product is a new graph obtained by grafting a copy of the finger into each vertex of the backbone. We study the comb graphs in the case when both components are the paths of order n and k, respectively, as well as the above comb graphs with an infinite ray attached to some of their vertices. A detailed spectral analysis is carried out in both situations. [ABSTRACT FROM AUTHOR]

Despite the growing prevalence of causal mapping procedures in the organizational strategy field and the growing body of research on entrepreneurial cognition, there have been surprisingly few investigations on how scholars might use causal cognitive mapping to elicit entrepreneurs' cognition. Based on the complementarity between the visual graph method and the matrix-multiplication method, this article outlines an integrative method that both overcomes the methodological issues of causal cognitive mapping and expands the qualitative methods used in the field of entrepreneurial cognition. By performing an empirical comparison, this article provides step-by-step guidance to empower scholars who either choose between these two methods or seek to use these methods in a complementary manner. Particular emphasis is placed on the methodological contributions that expand the entrepreneurial cognition toolbox. The methodological limits and potential improvements of these two methods regarding causal mapping are discussed. [ABSTRACT FROM AUTHOR]

For measuring the centrality in a digraph, Bonacich and Lloyd summarized a vector, from the power series of an attenuated adjacency matrix, as the alpha centrality. However, scores of alpha centrality are usually dominated by nodes in the strongly connected component, which owns the largest eigenvalue of the adjacency matrix. In this paper, based on reachability between strongly connected components, we consider not only the largest eigenvalue but also the other smaller ones to attenuate the adjacency matrix hierarchically; and obtain a measure from the power series of the hierarchically attenuated adjacency matrix. Consequently, we propose the hierarchical alpha centrality, which can yield higher scores for nodes at higher hierarchies of reachability in a digraph. [ABSTRACT FROM AUTHOR]

In this paper we consider strongly regular graphs G which admit a decomposition into two strongly regular graphs such that one of them, say H, is a star complement of G. Relations between the parameters of graphs paired in this way are determined. We also consider several particular types of strongly regular graph and determine whether such graphs can appear in the role of G or H. [ABSTRACT FROM AUTHOR]

Topological multiple correspondence analysis (TMCA) studies a group of categorical variables defined on the same set of individuals. It is a topological method of data analysis that consists of exploring, analyzing, and representing the associations between several qualitative variables in the context of multiple correspondence analysis (MCA). It compares and classifies proximity measures to select the best one according to the data under consideration, then analyzes, interprets, and visualizes with graphic representations, the possible associations between several categorical variables relating to the known problem of MCA. Based on the notion of neighborhood graphs, some of these proximity measures are more-or-less equivalent. A topological equivalence index between two measures is defined and statistically tested according to the degree of description of the associations between the modalities of these qualitative variables. We compare proximity measures and propose a topological criterion for choosing the best association measure, adapted to the data considered, from among some of the most widely used proximity measures for categorical data. The principle of the proposed approach is illustrated using a real dataset with conventional proximity measures for binary variables from the literature. The first step is to find the proximity measure that can best be adapted to the data; the second step is to use this measure to perform the TMCA. [ABSTRACT FROM AUTHOR]

Let be a symmetric matrix, or equivalently, a weighted graph whose edge ij has the weight. The eigenvalues of are the eigenvalues of M. We denote by the principal submatrix of M obtained by deleting from M both the ith row and the ith column. If μ is an eigenvalue of M, and thus of , of multiplicity , then vertex i of is a downer, or a neutral, or a Parter vertex, depending whether the multiplicity of μ in or, equivalently, in , is k−1, k, or k+1, respectively. In this paper, for a fixed μ, we consider vertex types according to the above classification in graphs which are generalized lexicographic products of an arbitrary graph over cliques and co-cliques, or connected regular graphs. In addition, we add some comments on constructions of large families of cospectral and integral graphs. [ABSTRACT FROM AUTHOR]

A cograph is a simple graph which contains no path on 4 vertices as an induced subgraph. We consider the eigenvalues of adjacency matrices of cographs and prove that a graph G is a cograph if and only if no induced subgraph of G has an eigenvalue in the interval. It is also shown that the multiplicity of any eigenvalue of a cograph G does not exceed the sum of multiplicities of 0 and as eigenvalues of G. We introduce a partial order on the vertex set of graphs G in terms of inclusions among the open and closed neighbourhoods of vertices, and conjecture that the multiplicity of any eigenvalue of a cograph G except for does not exceed the maximum size of an antichain with respect to that partial order. In two extreme cases (in particular for threshold graphs), the conjecture is shown to be true. Finally, we prove that bipartite -free graphs have no eigenvalue in the intervals and (0, 1 / 2). [ABSTRACT FROM AUTHOR]

Let be a signed graph, where G is the underlying simple graph and is the sign function on the edges of G. The adjacency matrix of a signed graph has or for adjacent vertices, depending on the sign of the connecting edges. In this paper, the eigenvalues of signed complete graphs are investigated. We prove that and 1 are the eigenvalues of the signed complete graph with the multiplicity at least t if there are vertices whose all incident edges are positive or negative, respectively. We study the spectrum of a signed complete graph whose negative edges induce an r-regular subgraph H. We obtain a relation between the eigenvalues of this signed complete graph and the eigenvalues of H. [ABSTRACT FROM AUTHOR]

For a sequence of adjacency matrices, describing the unfolding of a network from the graph of a star, through graphs of a broom, to the graph of a link with constant vertices and edges, we show that the leading eigenvalue (the spectral radius) satisfies a simple algebraic equation. The equation allows easy numerical computation of the leading eigenvalue as well as a direct proof of its monotonicity in terms of the maximal degree of vertices. [ABSTRACT FROM AUTHOR]

Let be a finite-dimensional Hilbert space and be a finite frame for . For , we associate a simple graph denoted by and called frame graph, with all elements of as vertices, and two distinct vertices are adjacent when the inner product of them is nonzero. The associated graph is called a tight frame graph if the mentioned frame is tight. In this paper, we study some basic properties of and investigate the relation between the frame-theoretic properties of and the graph-theoretic properties of . For example, it is shown that trees on more than two vertices and cycles on more than five vertices are not tight frame graphs while complete graphs, complete graphs minus a single edge and the join of each graph with itself are tight frame graphs. [ABSTRACT FROM AUTHOR]

In this article, we employ a regression formulation to estimate the high-dimensional covariance matrix for a given network structure. Using prior information contained in the network relationships, we model the covariance as a polynomial function of the symmetric adjacency matrix. Accordingly, the problem of estimating a high-dimensional covariance matrix is converted to one of estimating low dimensional coefficients of the polynomial regression function, which we can accomplish using ordinary least squares or maximum likelihood. The resulting covariance matrix estimator based on the maximum likelihood approach is guaranteed to be positive definite even in finite samples. Under mild conditions, we obtain the theoretical properties of the resulting estimators. A Bayesian information criterion is also developed to select the order of the polynomial function. Simulation studies and empirical examples illustrate the usefulness of the proposed methods. [ABSTRACT FROM AUTHOR]

In this paper we focus on connected signed graphs of fixed number of vertices, positive edges and negative edges that maximize the largest eigenvalue (also called the index) of their adjacency matrix. In the first step we determine these signed graphs in the set of signed generalized theta graphs. Concerning the general case, we use the eigenvector techniques for getting some structural properties of resulting signed graphs. In particular, we prove that positive edges induce nested split subgraphs, while negative edges induce double nested signed subgraphs.We observe that our concept can be applied when considering balancedness of signed graphs (the property that is extensively studied in both mathematical and non-mathematical context). [ABSTRACT FROM AUTHOR]

We give sharp upper and lower bounds for the spectral radius of a nonnegative matrix with positive row sums using average 3-row sums, compare these bounds with the existing bounds using the average 2-row sums by examples, and apply them to the adjacency matrix and the signless Laplacian matrix of a digraph or a graph. [ABSTRACT FROM AUTHOR]

A weighted Bethe graphBis obtained from a weighted generalized Bethe tree by identifying each set of children with the vertices of a graph belonging to a familyFof graphs. The operation of identifying the root vertex of each ofrweighted Bethe graphs to the vertices of a connected graphof orderris introduced as the-concatenation of a family ofrweighted Bethe graphs. It is shown that the Laplacian eigenvalues (whenFhas arbitrary graphs) as well as the signless Laplacian and adjacency eigenvalues (when the graphs inFare all regular) of the-concatenation of a family of weighted Bethe graphs can be computed (in a unified way) using the stable and low computational cost methods available for the determination of the eigenvalues of symmetric tridiagonal matrices. Unlike the previous results already obtained on this topic, the more general context of families of distinct weighted Bethe graphs is herein considered. [ABSTRACT FROM PUBLISHER]

In the high-speed urbanization process of China, the urban population has been increasing significantly, leading to a high-density aggregation of population. However, the sharp increase in population density has not produced commensurate improvements in the road networks. On the contrary, the population increase induced a serious evacuation vulnerability, which cities experience during various hazards and catastrophic events. Therefore, research on evacuation vulnerability is important to urban planning. To assess the evacuation vulnerability, the optimal and worst scenarios should be considered because all possible evacuation plans occur between these extremes. However, most previous evacuation vulnerability studies are based on the worst-case scenario, only providing an upper bound of a potential evacuation assessment. To provide a more comprehensive theoretical basis for decision-makers to understand the consequences caused by all possible evacuations, this paper proposes an optimal evacuation vulnerability assessment model that provides the lower bound on potential evacuation difficulties. The model is solved by a stepwise spreading algorithm based on Graph Theory. Subsequently, to evaluate the effectiveness of the model, the study adopts the model to assess the evacuation capability of different road network topologies. A comparison with previous research was performed. The model was demonstrated in an application to the South Luogu Alley of Beijing, China. The significance of this paper is that the combination of our model with previous research may provide a more complete theoretical basis for an evacuation vulnerability assessment. [ABSTRACT FROM AUTHOR]

Graphs with least eigenvalue greater than or equal toare to a big extent studied by Hoffman and other authors from the early beginning of the spectral graph theory. Most of these results are summarized in the monograph [Cvetković D, Rowlinson P, Simić S. Spectral generalizations of line graphs, on graphs with least eigenvalue, Cambridge University Press, 2004], and the survey paper [Cvetković D, Rowlinson P, Simić S. Graphs with least eigenvalue: ten years on, Linear Algebra Appl. 2015;484:504–539] which is aimed to cover the next 10 years since their monograph appeared. Here, we add some further results. Among others, we identify graphs whose least eigenvalue is greater than, but closest towithin the graphs of fixed order. Some consequences of these considerations are found in the context of the highest occupied molecular orbital–lowest unoccupied molecular orbital invariants. [ABSTRACT FROM AUTHOR]

A graphis nonsingular if its adjacency matrixis nonsingular. A nonsingular graphis said to have an inverseifis signature similar to a nonnegative matrix. An-graphis a bipartite graph with a unique perfect matching. We introduce the ‘even’ness of a nonmatching edge and show that under certain conditions a connected-graph has an inverse if and only ifis bipartite, whereis the set of all even nonmatching edges. This extends some known results, providing us with a larger class of graphs possessing inverses. [ABSTRACT FROM PUBLISHER]

A signed graphconsists of an underlying graphand a sign function, which assigns each edge ofa sign, either positive or negative. The adjacency matrix of a signed graphis defined aswith, whereis the adjacency matrix of the underlying graph. The rank ofis defined to be the rank of. In this paper, we characterize the signed graphs with rankor, and characterize the signed planar graphs with rank 4. [ABSTRACT FROM PUBLISHER]

Letandbe two vertex disjoint graphs of ordersandrespectively, whereandLetbe a specified edge ofsuch thatis isomorphic toLetbe a subset of the edge set ofand letdenote the subgraph ofinduced byLetbe the graph obtained by taking one copy ofandvertex disjoint copies ofand then pasting the edgein theth copy ofwith the edgewhereThen the copies of the graphthat are pasted to the edgesare called as edge-pockets, and we sayis a graph withedge-pockets. In this article, we prove some results describing the Laplacian (resp. adjacency) spectrum ofusing the Laplacian (resp. adjacency) spectra ofandThe complete Laplacian (resp. adjacency) spectrum ofis also described in some particular cases. As an application, we show that these results enable us to construct infinitely many pairs of Laplacian (resp. adjacency) cospectral graphs. [ABSTRACT FROM AUTHOR]

We develop majorisation results that characterise changes in eigenvector components of a graph's adjacency matrix when its topology is changed. Specifically, for general (weighted, directed) graphs, we characterise changes in dominant eigenvector components for single- and multi-row incrementations. We also show that topology changes can be tailored to set ratios between the components of the dominant eigenvector. For more limited graph classes (specifically, undirected, and reversibly-structured ones), majorisations for components of the subdominant and other eigenvectors upon graph modifications are also obtained. [ABSTRACT FROM PUBLISHER]

A block graph is a graph in which every block is a complete graph. Letbe a block graph and letbe the adjacency matrix of. We first obtain a formula for the determinant ofover reals. It is shown thatis nonsingular overif and only if the removal of any vertex fromproduces a graph with exactly one odd component. A formula for the inverse ofoveris obtained, whenever it exists. We obtain some results for the adjacency matrices over, of claw-free block graphs, which are the same as the line graphs of trees, and for the adjacency matrices of flowers, which are block graphs with only one cut-vertex. [ABSTRACT FROM AUTHOR]

Two graphs are said to be A-cospectral if they have the same adjacency spectrum. A graphGis said to be determined by its adjacency spectrum if there is no other non-isomorphic graph A-cospectral withG. A tree is called starlike if it has exactly one vertex of degree greater than 2. In this article, we prove that the line graphs of starlike trees with maximum degree at least 12 are determined by their adjacency spectra. [ABSTRACT FROM AUTHOR]

The nullity η(G) of a graph G is the multiplicity of zero as an eigenvalue of the adjacency matrix of G. If η(G)= 1, then the core of G is the subgraph induced by the vertices associated with the nonzero entries of the kernel eigenvector. The set of vertices which are not in the core is the periphery of G. A graph G with nullity one is minimal configuration if no two vertices in the periphery are adjacent and deletion of any vertex in the periphery increases the nullity. An ∞-graph ∞(p, l, q) is a graph obtained by joining two vertex-disjoint cycles Cp and Cq by a path of length l≥ 0. Let B* be the class of bicyclic graphs with an ∞-graph as an induced subgraph. In this article, we characterize the graphs in B* which are minimal configurations. [ABSTRACT FROM AUTHOR]

The signless Laplacian matrix of a graph is defined to be the sum of its adjacency matrix and degree matrix. Let [image omitted] be the set of all the connected graphs of order n and diameter d and Gn,k the set of all connected graphs with order n and k cut vertices. In this article, we determine the graphs that have the maximal signless Laplacian spectral radius and give the upper bounds of graphs in these two sets. [ABSTRACT FROM AUTHOR]

We characterize all regular graphs whose second largest eigenvalue does not exceed 1. In the sequel, we determine all coronas, different from cones, with the same property. Some results and examples regarding unsolved cases are also given. [ABSTRACT FROM AUTHOR]

In this note we show how to construct two distinct bipartite graphs which are cospectral for both the adjacency and normalized Laplacian matrices by 'unfolding' a base bipartite graph in two different ways. [ABSTRACT FROM AUTHOR]

This research implements a method, based on Dioid algebra, of transferring progress control policies for a class of repetitive discrete event systems. Commonly used policies include one that requires precedence constraints with respect to processing order relations, and another in which relative processing start and completion times for all facilities are specified. In conventional methods, however, the framework for handling the state equation differs, depending on which policy is used. These policies are thus distinct, and cannot as yet be treated in a unified manner. This research proposes a method of transferring the transition matrices by using common parameter matrices and vectors, and implements a method of transferring the progress control policy per job. [ABSTRACT FROM AUTHOR]

In this article we follow the study of the hierarchical product of graphs, an operation recently introduced in the context of networks. A well-known example of such a product is the binomial tree which is the (hierarchical) power of the complete graph on two vertices. An appealing property of this structure is that all the eigenvalues are distinct. Here we show how to obtain a graph with this property by applying the hierarchical product. In particular, we propose a generalization of the binomial tree and study some of its main properties. [ABSTRACT FROM AUTHOR]

A graph G is singular with nullity η(G), if zero is an eigenvalue of its adjacency matrix with multiplicity η(G). If η(G) = 1, then the core of G is the subgraph induced by the vertices associated with the non-zero entries of the kernel eigenvector. The set of vertices which are not in the core is called the periphery of G. A graph G with nullity one is called a minimal configuration if no two vertices in the periphery are adjacent and deletion of any vertex in the periphery increases the nullity. In this article, we describe the structure of a singular unicyclic graph and single out the class of unicyclic graphs which are minimal configurations. [ABSTRACT FROM AUTHOR]

Business processes and its related workflow systems have received greater interest in practice and research in the last decade. Many analytical methodologies for analysis and design of workflow systems emerged. A recent formal approach to study workflows using a graph-theoretic method called 'metagraphs' has demonstrated effectiveness for analysing connectivity and interactions of information and resources between workflow components. However, past works in analysis of metagraph are element-based. Since nodes in metagraphs represent either the input or output of an activity it is natural to process information contained in a node taken as a unit. This paper takes a node-centric view on metagraphs that is a major departure from the element-based approach today. The change in focus requires provisioning an analysis framework under the node-centric views. New basic constructs including, but not limited to, concepts such as: 'surplus sets', 'deficit sets', 'state of a path', and 'node-centric view of adjacency matrices' are introduced. The approach produces computational feasible systems for elements that are over supplied and/or under supplied from a source node to a target node of any path of the metagraph. Such information could be valuable for designing workflow systems. Also, the node-centric approach is shown to be an extension of the basic constructs of element-view metagraphs and is a complementary method for validating information requirements of workflow modelling. Illustrative examples are given. [ABSTRACT FROM AUTHOR]

We consider the problem of reconstructing the characteristic polynomial of a graph G from its polynomial deck, i.e. the collection of characteristic polynomials of its vertex-deleted subgraphs. Here we provide a positive solution for all unicyclic graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph. Let A(G) be the adjacency matrix of G . We give a combinatorial description of A ( G )-1 of a bipartite graph G with a unique perfect matching. As a corollary, we obtain the combinatorial description of the inverse of a nonsingular tree. A graph is said to have property (R) if 1/λis an eigenvalue of G whenever  λ  is an eigenvalue of G . Further, if  λ  and have the same multiplicity, for each eigenvalue  λ  then it is said to have the property (SR). We characterize all trees with property (R) and show that it is exactly the class of all trees with property (SR). The class of trees with property (R) is also identical to the class of corona trees, namely, the trees which can be obtained from other trees by adding pendants to all vertices. Other equivalent conditions for a tree to have property (R) are also given. [ABSTRACT FROM AUTHOR]

A graph is singular of nullity η if zero is an eigenvalue of its adjacency matrix with multiplicity η. If η( G )=1, then the core of G is the subgraph induced by the vertices associated with the non-zero entries of the zero-eigenvector. A connected subgraph of G with the least number of vertices and edges, that has nullity one and the same core as G , is called a minimal configuration. A subdivision of a graph G is obtained by inserting a vertex on every edge of G . We review various properties of minimal configurations. In particular, we show that a minimal configuration is a tree if and only if it is a subdivision of some other tree. [ABSTRACT FROM AUTHOR]