We complete the determination of the signed graphs for which the adjacency matrix has all but at most two eigenvalues equal to ±1. The unsigned graphs and the disconnected, the bipartite and the ...complete signed graphs with this property have already been determined in two earlier papers. Here we deal with the remaining cases.
Laplacian energy of a graph Gutman, Ivan; Zhou, Bo
Linear algebra and its applications,
04/2006, Letnik:
414, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Let
G be a graph with
n vertices and
m edges. Let
λ
1,
λ
2,
…
,
λ
n
be the eigenvalues of the adjacency matrix of
G, and let
μ
1,
μ
2,
…
,
μ
n
be the eigenvalues of the Laplacian matrix of
G. An ...earlier much studied quantity
E
(
G
)
=
∑
i
=
1
n
|
λ
i
|
is the
energy of the graph
G. We now define and investigate the
Laplacian energy as
LE
(
G
)
=
∑
i
=
1
n
|
μ
i
-
2
m
/
n
|
. There is a great deal of analogy between the properties of
E(
G) and
LE(
G), but also some significant differences.
A mixed extension of a graph G is a graph H obtained from G by replacing each vertex of G by a clique or a coclique, where vertices of H coming from different vertices of G are adjacent if and only ...if the original vertices are adjacent in G. If G has no more than three vertices, H has all but at most three adjacency eigenvalues equal to 0 or −1. In this paper we consider the converse problem, and determine the class G of all graphs with at most three eigenvalues unequal to 0 and −1. Ignoring isolated vertices, we find that G consists of all mixed extensions of graphs on at most three vertices together with some particular mixed extensions of the paths P4 and P5.
We analyze graphs attaining the extreme values of various spectral indices in the class of all simple connected graphs, as well as in the class of graphs which are not complete multipartite graphs. ...We also present results on density of spectral gap indices and its nonpersistency with respect to small perturbations of the underlying graph. We show that a small change in the set set of edges may result in a significant change of the spectral index like, e.g., the spectral gap or spectral index. We also present a statistical and numerical analysis of spectral indices of graphs of the order m≤10. We analyze the extreme values for spectral indices for graphs and their small perturbations. Finally, we present the statistical and extreme properties of graphs on m≤10 vertices.
We present the first steps towards the determination of the signed graphs for which the adjacency matrix has all but at most two eigenvalues equal to ±1. Here we deal with the disconnected, the ...bipartite and the complete signed graphs. In addition, we present many examples which cannot be obtained from an unsigned graph or its negative by switching.
A graph G is said to be determined by its generalized spectra (DGS for short) if for any graph H, H and G are cospectral with cospectral complements implies H is isomorphic to G. In Wang (2017) 14, ...the author gave a simple condition for a graph to be DGS. More precisely, let G be a n-vertex graph with adjacency matrix AG, and let W=e,AGe,…,AGn−1e be the walk-matrix of G, where e is the all-one vector. A theorem of Wang states that if 2−⌊n/2⌋detW is odd and square-free, then G is DGS.
However, the above theorem fails for regular graphs. In this paper, we first generalize the notion of DGS by introducing a new matrix associated with graph G, which is essentially a rank-one perturbation of the adjacency matrix of G and is obtained by introducing a graph-vectorξG associated with G. For a fixed graph-vector ξG, define Φ(G)=det(λI−(AG+tξGξGT)). A graph G is determined byΦ(G) (Φ-DS for short) if for any graph H, Φ(G)=Φ(H) implies that H is isomorphic to G. It is not difficult to show that if ξG is the all-one vector, then G is Φ-DS if and only if it is DGS. Thus, the notion of Φ-DS generalizes that of DGS in a natural way. Moreover, we give a simple arithmetic condition for a large family of regular graphs to be Φ-DS, which is analogous to the aforementioned theorem. Numerical experiments are also presented to illustrate the effectiveness of our results.
On Randić energy Gutman, Ivan; Furtula, Boris; Bozkurt, Ş. Burcu
Linear algebra and its applications,
02/2014, Letnik:
442
Journal Article
Recenzirano
Odprti dostop
The Randić matrix R=(rij) of a graph G whose vertex vi has degree di is defined by rij=1/didj if the vertices vi and vj are adjacent and rij=0 otherwise. The Randić energy RE is the sum of absolute ...values of the eigenvalues of R. RE coincides with the normalized Laplacian energy and the normalized signless-Laplacian energy. Several properties or R and RE are determined, including characterization of graphs with minimal RE. The structure of the graphs with maximal RE is conjectured.
Effective graph resistance Ellens, W.; Spieksma, F.M.; Van Mieghem, P. ...
Linear algebra and its applications,
11/2011, Letnik:
435, Številka:
10
Journal Article
Recenzirano
Odprti dostop
This paper studies an interesting graph measure that we call the effective graph resistance. The notion of effective graph resistance is derived from the field of electric circuit analysis where it ...is defined as the accumulated effective resistance between all pairs of vertices. The objective of the paper is twofold. First, we survey known formulae of the effective graph resistance and derive other representations as well. The derivation of new expressions is based on the analysis of the associated random walk on the graph and applies tools from Markov chain theory. This approach results in a new method to approximate the effective graph resistance. A second objective of this paper concerns the optimisation of the effective graph resistance for graphs with given number of vertices and diameter, and for optimal edge addition. A set of analytical results is described, as well as results obtained by exhaustive search. One of the foremost applications of the effective graph resistance we have in mind, is the analysis of robustness-related problems. However, with our discussion of this informative graph measure we hope to open up a wealth of possibilities of applying the effective graph resistance to all kinds of networks problems.
PDF
