Let
G be a graph on
n vertices
v
1,
v
2,…,
v
n
and let
d(
v
i
) be the degree (= number of first neighbors) of the vertex
v
i
. If (
d(
v
1),
d(
v
2),…,
d(
v
n
))
t is an eigenvector of the ...(0,1)-adjacency matrix of
G, then
G is said to be harmonic. Earlier all harmonic trees were determined; their number is infinite. We now show that for any
c,
c>1
, the number of connected harmonic graphs with cyclomatic number
c is finite. In particular, there are no connected non-regular unicyclic and bicyclic harmonic graphs and there exist exactly four and eighteen connected non-regular tricyclic and tetracyclic harmonic graphs.
ESTRADA INDEX OF ITERATED LINE GRAPHS ALEKSIĆ, TATJANA; GUTMAN, I.; PETROVIĆ, M.
Bulletin de l'Académie serbe des sciences, Classe des sciences mathématiques et naturelles. Sciences mathématiques,
01/2007
32
Journal Article
Peer reviewed
If λ₁, λ₂, . . ., λn are the eigenvalues of a graph G, then the Estrada index of G is $EE\left( G \right) = \sum\limits_{i = 1}^n {{e^{\lambda i}}} $. If L(G) = L¹(G) is the line graph of G, then the ...iterated line graphs of G are defined as Lk(G) = L(Lk-1(G)) for k = 2, 3, . . . . Let G be a regular graph of order n and degree r . We show that EE(Lk(G)) = ak(r) EE(G) + n bk(r) , where the multipliers ak(r) and bk(r) depend only on the parameters r and k. The main properties of ak(r) and bk(r) are established.
Combining Color and Topology for Partial Matching dos Santos, Dali F. D.; da Silva, Ilmerio R.; Guliato, D. ...
2012 IEEE 24th International Conference on Tools with Artificial Intelligence,
2012-Nov., Volume:
1
Conference Proceeding
Although, color is one of the most visually distinguishable visual properties, color alone is not enough to describe the content of images. The spatial organization of the different color regions ...also play an important role. In this paper, we propose and evaluate a new descriptor that combines information about color and about its spatial arrangement in an image. Moreover, the mechanism used to compute the descriptor provides support for partial matching of images and for the development of efficient retrieval systems. We first describe the spatial arrangement of the color regions using a topological graph, where vertices represent the color regions and edges represent connections between regions and also the color differences between them. To compute the descriptor from this graph representation we use the spectral graph theory, avoiding the need for direct graph comparison. We performed various experimental evaluations to compare the accuracy of our new descriptor with descriptors based only on color, based only on topological information and a combination of both.
The structure descriptor EE, put forward in 2000 by one of the present authors, is equal to the sum of the terms exp(li) over all eigenvalues li of the underlying (molecular) graph. Some basic ...properties of the EE-index are determined: lower and upper bounds for EE are obtained (valid for n-vertex graphs and for (n,m)-graphs), and the corresponding extremal graphs are characterized. Some relations between EE and graph energy are established.
Let G be a graph with adjacency matrix A(G) and with D(G) the diagonal matrix of its vertex degrees. Nikiforov defined the matrix Aα(G), with α∈0,1, asAα(G)=αD(G)+(1−α)A(G). The largest and the ...smallest eigenvalues of Aα(G) are respectively denoted by ρ(G) and λn(G). In this paper, we present a tight upper bound for ρ(G) in terms of the vertex degrees of G for α≠1. For any graph G,ρ(G)≤maxu∼w{α(du+dw)+α2(du+dw)2+4(1−2α)dudw2}. If G is connected, for α∈0,1), the equality holds if and only if G is regular or bipartite semi-regular. As an application, we solve the problem raised by Nikiforov in 15. For the smallest eigenvalue λn(G) of a bipartite graph G of order n with no isolated vertices, for α∈0,1), thenλn(G)≥minu∼w{α(du+dw)−α2(du+dw)2+4(1−2α)dudw2}. If G is connected and α≠1/2, the equality holds if and only if G is regular or semi-regular.
Let G be a graph with eigenvalues λ1(G)≥⋯≥λn(G). In this paper we investigate the value of λ3(G). We show that if the multiplicity of −1 as an eigenvalue of G is at most n−13, then λ3(G)≥0. We prove ...that λ3(G)∈{−2,−1,1−52} or −0.59<λ3(G)<−0.5 or λ3(G)>−0.496. We find that λ3(G)=−2 if and only if G≅P3 and λ3(G)=1−52 if and only if G≅P4, where Pn is the path on n vertices. In addition we characterize the graphs whose third largest eigenvalue equals −1. We find all graphs G with −0.59<λ3(G)<−0.5. Finally we investigate the limit points of the set {λ3(G): G is a graph such thatλ3(G)<0} and show that 0 and −0.5 are two limit points of this set.
Let Fq be a finite field with q=pe elements, where p is a prime and e≥1 is an integer. Let ℓ,n be two positive integers such that ℓ<n. Fix a monic polynomial u(x)=xn+un−1xn−1+⋯+uℓ+1xℓ+1∈Fqx of degree ...n and consider all degree n monic polynomials of the formf(x)=u(x)+vℓ(x),vℓ(x)=aℓxℓ+aℓ−1xℓ−1+⋯+a1x+a0∈Fqx. For any non-negative integer k≤min{n,q}, let Nk(u(x),ℓ) denote the total number of vℓ(x) such that u(x)+vℓ(x) has exactly k distinct roots in Fq, i.e.Nk(u(x),ℓ)=|{f(x)=u(x)+vl(x)|f(x)has exactlykdistinct zeros inFq}|. In this paper, we obtain explicit combinatorial formulae for Nk(u(x),ℓ) when n−ℓ is small, namely when n−ℓ=1,2,3. As an application, we define two kinds of Wenger graphs called jumped Wenger graphs and obtain their explicit spectrum.
For a simple connected graph G with n -vertices having Laplacian eigenvalues μ 1 , μ 2 , … , μ n−1 , μ n =0 , and signless Laplacian eigenvalues q 1 ,q 2 ,…,q n , the ...Laplacian-energy-like invariant(LEL ) and the incidence energy (IE ) of a graph G are respectively defined as LEL(G)=∑ n−1 i=1 μ i − − √ and IE(G)=∑ n i=1 q i √ . In this paper, we obtain some sharp lower and upper bounds for the Laplacian-energy-like invariant and incidence energy of a graph.
PDF
