The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. In this paper we study the difference of energies of a (regular) graph G and its ...complete graph G‾, that is, E(G)−E(G‾). In particular, we provide the answer to Problem 12 raised in Nikiforov (2016) 18. Moreover, we give a lower bound for the energy of a regular graph in terms of the order and the clique cover number.
Using the notions of clique partitions and edge clique covers of graphs, we consider the corresponding incidence structures. This connection furnishes lower bounds on the negative eigenvalues and ...their multiplicities associated with the adjacency matrix, bounds on the incidence energy, and on the signless Laplacian energy for graphs. For the more general and well-studied set S(G) of all real symmetric matrices associated with a graph G, we apply an extended version of an incidence matrix tied to an edge clique cover to establish several classes of graphs that allow two distinct eigenvalues.
Symmetric Pascal matrices and related graphs Cheon, Gi-Sang; Kim, Jang Soo; Mojallal, Seyed Ahmad ...
Linear & multilinear algebra,
12/2022, Volume:
70, Issue:
21
Journal Article
Peer reviewed
The symmetric Pascal matrix is a square matrix whose entries are given by binomial coefficients modulo 2. In 1997, Christopher and Kennedy defined and studied the binomial graph, which is the graph ...whose adjacency matrix is the symmetric Pascal matrix. They computed the spectrum of the binomial graph of order a power of 2. In this paper, we study spectral properties of the binomial graph of any order such as eigenvalues and eigenvectors, algebraic connectivities and inertia indices. We also compute the determinant of the symmetric Pascal matrix in modulo 3.
For a graph G, we associate a family of real symmetric matrices, S(G), where for any A∈S(G), the location of the nonzero off-diagonal entries of A are governed by the adjacency structure of G. Let ...q(G) be the minimum number of distinct eigenvalues over all matrices in S(G). In this work, we give a characterization of all connected threshold graphs G with q(G)=2. Moreover, we study the values of q(G) for connected threshold graphs with trace 2, 3, n−2, n−3, where n is the order of threshold graph. The values of q(G) are determined for all connected threshold graphs with 7 and 8 vertices with two exceptions. Finally, a sharp upper bound for q(G) over all connected threshold graph G is given.
In this corrigendum, we report and correct some errors in Theorems 3.1 and 4.1 and hence Corollaries 4.2 and 4.3 in Linear Algebra Appl. 595 (2020) 1–12.
Proximity π and remoteness ρ are respectively the minimum and the maximum, over the vertices of a connected graph, of the average distance from a vertex to all others. The distance eigenvalues of a ...connected graph G, denoted by ∂1≥∂2≥⋯≥∂n, are those of its distance matrix. In this paper, we prove π+∂3>0 for any graph with a diameter at least 3. This result leads to relations between ∂3 and several distance invariants of a graph such as remoteness, diameter, radius, average eccentricity and average distance. In particular, it confirms ρ+∂3>0 for any graph with a diameter at least 3 conjectured by Aouchiche and Hansen (2016).
Let G be a graph of order n. Also let λ1≥λ2≥⋯≥λn be the eigenvalues of graph G. In this paper, we present the following upper bound on the sum of the k(≤n) largest eigenvalues of G in terms of the ...order n and negative inertia θ (the number of negative eigenvalues): ∑i=1kλi≤n2(θ+1)(θ+θ(kθ+k−1)) with equality holding if and only if G≅nK1 or G≅pK‾t(n=pt,p≥2) with k=1 (where pK‾t is the complete p-partite graph of p t vertices with all partition sets having size t). Moreover, we obtain a sharp upper bound on the energy of bipartite graphs with given order n and rank r. We also propose an open problem as follows:
Characterize all connected d-regular bipartite graphs of order n with 5 distinct eigenvalues and rank r=2n2(4d−n)2, where d>n4.
Finally we give a partial solution to this problem.
On Laplacian energy of graphs Das, Kinkar Ch; Mojallal, Seyed Ahmad
Discrete mathematics,
06/2014, Volume:
325
Journal Article
Peer reviewed
Open access
Let G be a graph with n vertices and m edges. Also let μ1,μ2,…,μn−1,μn=0 be the eigenvalues of the Laplacian matrix of graph G. The Laplacian energy of the graph G is defined as ...LE=LE(G)=∑i=1n|μi−2mn|. In this paper, we present some lower and upper bounds for LE of graph G in terms of n, the number of edges m and the maximum degree Δ. Also we give a Nordhaus–Gaddum-type result for Laplacian energy of graphs. Moreover, we obtain a relation between Laplacian energy and Laplacian-energy-like invariant of graphs.
The energy of a simple graph G, E(G), is the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of line graph and the signless Laplacian energy of graph G are denoted ...by E(LG) (LG is the line graph of G) and LE+(G), respectively. In this paper we obtain a relation between E(LG) and LE+(G) of graph G. From this relation we characterize all the graphs satisfying E(LG)=LE+(G)+4mn−4. We also present a relation between E(G) and E(LG). Moreover, we give an upper bound on E(LG) of graph G and characterize the extremal graphs.