Search

A graph G is said to be determined by the spectrum of its Laplacian matrix (DLS) if every graph with the same spectrum is isomorphic to G. In some recent papers it is proved that the friendship graphs and starlike trees are DLS. If a friendship graph and a starlike tree are joined by merging their vertices of degree greater than two, then the resulting graph is called a path-friendship graph. In this paper, it is proved that the path-friendship graphs, a natural generalization of friendship graphs and starlike trees, are also DLS. Consequently, using these results we provide a solution for an open problem.

The main goal of the paper is to answer an unsolved problem. A multicone graph is defined to be the join of a clique and a regular graph, and a wheel as the join of a vertex and a cycle. In this study, we present new classes of multicone graphs that are natural generalizations of wheel graphs and we show that they are determined by their adjacency spectra as well as their Laplacian spectra. We also show that the complements of some of these graphs are determined by their adjacency spectra. In addition, we give a necessary and sufficient condition for perfect graphs cospectral with some of the graphs investigated in the paper. Finally, we conclude with two problems for further study.

A universal adjacency matrix of a graph G with adjacency matrix A is any matrix of the form U = α A + β I + γ J + δ D with α ≠ 0 , where I is the identity matrix, J is the all-ones matrix and D is the diagonal matrix with the vertex degrees. In the case that G is the disjoint union of regular graphs, we present an expression for the characteristic polynomials of the various universal adjacency matrices in terms of the characteristic polynomials of the adjacency matrices of the components. As a consequence we obtain a formula for the characteristic polynomial of the Seidel matrix of G, and the signless Laplacian of the complement of G (i.e. the join of regular graphs). The main tool is a simple but useful lemma on equitable matrix partitions. With this note we also want to propagate this technique.

Let G be a simple graph on n vertices. An independent set in a graph is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial I(G,x)=∑k=0ns(G,k)xk$I(G,x) = \sum\nolimits_{k = 0}^n {s\left({G,k} \right)x^k }$, where s(G, k) is the number of independent sets of G with size k and s(G, 0) = 1. A unicyclic graph is a graph containing exactly one cycle. Let Cn be the cycle on n vertices. In this paper we study the independence polynomial of unicyclic graphs. We show that among all connected unicyclic graphs G on n vertices (except two of them), I(G, t) > I(Cn, t) for sufficiently large t. Finally for every n ≥ 3 we find all connected graphs H such that I(H, x) = I(Cn, x).

A starlike tree is a tree with exactly one vertex of degree greater than two. The spectral radius of a graph G, that is denoted by $$\lambda (G)$$ , is the largest eigenvalue of G. Let k and $$n_1,\ldots ,n_k$$ be some positive integers. Let $$T(n_1,\ldots ,n_k)$$ be the tree T (T is a path or a starlike tree) such that T has a vertex v so that $$T{\setminus } v$$ is the disjoint union of the paths $$P_{n_1-1},\ldots ,P_{n_k-1}$$ where every neighbor of v in T has degree one or two. Let $$P=(p_1,\ldots ,p_k)$$ and $$Q=(q_1,\ldots ,q_k)$$ , where $$p_1\ge \cdots \ge p_k\ge 1$$ and $$q_1\ge \cdots \ge q_k\ge 1$$ are integer. We say P majorizes Q and let $$P\succeq _M Q$$ , if for every j, $$1\le j\le k$$ , $$\sum _{i=1}^{j}p_i\ge \sum _{i=1}^{j}q_i$$ , with equality if $$j=k$$ . In this paper we show that if P majorizes Q, that is $$(p_1,\ldots ,p_k)\succeq _M(q_1,\ldots ,q_k)$$ , then $$\lambda (T(q_1,\ldots ,q_k))\ge \lambda (T(p_1,\ldots ,p_k))$$ .

Let $$k\ge 1$$ and $$n_1,\ldots ,n_k\ge 1$$ be some integers. Let $$S(n_1,\ldots ,n_k)$$ be a tree T such that T has a vertex v of degree k and $$T{\setminus } v$$ is the disjoint union of the paths $$P_{n_1},\ldots ,P_{n_k}$$ , that is $$T{\setminus } v\cong P_{n_1}\cup \cdots \cup P_{n_k}$$ so that every neighbor of v in T has degree one or two. The tree $$S(n_1,\ldots ,n_k)$$ is called starlike tree, a tree with exactly one vertex of degree greater than two, if $$k\ge 3$$ . In this paper we obtain the eigenvalues of starlike trees. We find some bounds for the largest eigenvalue (for the spectral radius) of starlike trees. In particular we prove that if $$k\ge 4$$ and $$n_1,\ldots ,n_k\ge 2$$ , then $$\frac{k-1}{\sqrt{k-2}}

In this paper we characterize all graphs with exactly two non-negative eigenvalues. As a consequence we obtain all graphs ?$G$? such that ?$\lambda_3(G) < 0$?, where ?$\lambda_3(G)$? is the third largest eigenvalue of ?$G$?. V članku karakteriziramo vse grafe z natanko dvema nenegativnima lastnima vrednostima. Od tod dobimo vse grafe ?$G$?, za katere je ?$\lambda_3(G) < 0$?, kjer je ?$\lambda_3(G)$? tretja največja lastna vrednost grafa ?$G$?.

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 − 5 2 } or − 0.59 λ 3 ( G ) − 0.5 or λ 3 ( G ) > − 0.496 . We find that λ 3 ( G ) = − 2 if and only if G ≅ P 3 and λ 3 ( G ) = 1 − 5 2 if and only if G ≅ P 4 , where P n 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 G be a graph of order n . A dominating set of G is a subset of vertices of G , say S , such that every vertex in V ( G ) ? S is adjacent to at least one vertex of S . The domination polynomial of G is the polynomial D ( G , x ) = ? i = 1 n d ( G , i ) x i , where d ( G , i ) is the number of dominating sets of G of size i . A root of D ( G , x ) is called a domination root of G . Let ? = ? ( G ) be the minimum degree of vertices of G . We prove that all roots of D ( G , x ) lies in the set { z : | z + 1 | ? 2 n - 1 ? + 1 } . We show that D ( G , x ) has at least ? - 1 non-real roots. In particular, we prove that if all roots of D ( G , x ) are real, then ? = 1 . We construct an infinite family of graphs such that all roots of their polynomials are real. Motivated by a conjecture (Akbari, et?al. 2010) which states that every integer root of D ( G , x ) is - 2 or 0, we prove that if ? ? 2 n 3 - 1 , then every integer root of D ( G , x ) is - 2 or 0. Also we prove that the conjecture is valid for trees and unicyclic graphs. Finally we characterize all graphs that their domination roots are integer.

In this paper we characterize all bipartite graphs with at most six non-zero eigenvalues. We determine the eigenvalues of bipartite graphs that have at most four nonzero eigenvalues. V tem članku karakteriziramo vse dvodelne grafe z največ šestimi neničelnimi lastnimi vrednostmi. Določimo lastne vrednosti dvodelnih grafov ki imajo največ štiri neničelne lastne vrednosti.

Richard Brualdi proposed in Stevanivic (2007) [10] the following problem: (Problem AWGS.4) Let GnGn and Gn′ be two nonisomorphic graphs on n vertices with spectra λ1≥λ2≥⋯≥λnandλ1′≥λ2′≥⋯≥λn′, respectively. Define the distance between the spectra of GnGn and Gn′ as λ(Gn,Gn′)=∑i=1n(λi−λi′)2(or use ∑i=1n|λi−λi′|). Define the cospectrality of GnGn by cs(Gn)=min⁡{λ(Gn,Gn′):Gn′ not isomorphic to Gn}. Let csn=max⁡{cs(Gn):Gn a graph on n vertices}. Problem A. Investigate cs(Gn)cs(Gn) for special classes of graphs. Problem B. Find a good upper bound on csncsn. In this paper we completely answer Problem B by proving that csn=2csn=2 for all n≥2n≥2, whenever csncsn is computed with respect to any lplp-norm with 1≤p

Richard Brualdi proposed in Stevanivic (2007) [6] the following problem: (Problem AWGS.4) Let GnGn and Gn′ be two nonisomorphic graphs on n vertices with spectra λ1⩾λ2⩾⋯⩾λnandλ1′⩾λ2′⩾⋯⩾λn′, respectively. Define the distance between the spectra of GnGn and Gn′ as λ(Gn,Gn′)=∑i=1n(λi−λi′)2(or use ∑i=1n|λi−λi′|). Define the cospectrality of GnGn by cs(Gn)=min{λ(Gn,Gn′):Gn′ not isomorphic to Gn}. Let csn=max{cs(Gn):Gn a graph on n vertices}. Problem A. Investigate cs(Gn)cs(Gn) for special classes of graphs. Problem B. Find a good upper bound on csncsn. In this paper we study Problem A and determine the cospectrality of certain graphs by the Euclidian distance. Let KnKn denote the complete graph on n vertices, nK1nK1 denote the null graph on n vertices and K2+(n−2)K1K2+(n−2)K1 denote the disjoint union of the K2K2 with n−2n−2 isolated vertices, where n⩾2n⩾2. In this paper we find cs(Kn)cs(Kn), cs(nK1)cs(nK1), cs(K2+(n−2)K1)cs(K2+(n−2)K1) (n⩾2n⩾2) and cs(Kn,n)cs(Kn,n).

Let G be a simple graph of order n and size m. An edge covering of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In this paper we introduce a new graph polynomial. The edge cover polynomial of G is the polynomial E(G,x)=@?"i"="1^me(G,i)x^i, where e(G,i) is the number of edge coverings of G of size i. Let G and H be two graphs of order n such that @d(G)>=n2, where @d(G) is the minimum degree of G. If E(G,x)=E(H,x), then we show that the degree sequence of G and H are the same. We determine all graphs G for which E(G,x)=E(P"n,x), where P"n is the path of order n. We show that if @d(G)>=3, then E(G,x) has at least one non-real root. Finally, we characterize all graphs whose edge cover polynomials have exactly one or two distinct roots and moreover we prove that these roots are contained in the set {-3,-2,-1,0}.

Let G be a simple graph of order n and size m . An edge covering of the graph G is a set of edges such that every vertex of the graph is incident to at least one edge of the set. Let e ( G , k ) be the number of edge covering sets of G of size k . The edge cover polynomial of G is the polynomial E ( G , x ) = ? k = 1 m e ( G , k ) x k . In this paper, we obtain some results on the roots of the edge cover polynomials. We show that for every graph G with no isolated vertex, all the roots of E ( G , x ) are in the ball { z ? C : | z | < ( 2 + 3 ) 2 1 + 3 ? 5.099 } . We prove that if every block of the graph G is K 2 or a cycle, then all real roots of E ( G , x ) are in the interval ( - 4 , 0 ] . We also show that for every tree T of order n we have ? R ( K 1 , n - 1 ) ? ? R ( T ) ? ? R ( P n ) , where - ? R ( T ) is the smallest real root of E ( T , x ) , and P n , K 1 , n - 1 are the path and the star of order n , respectively.

Let G be a graph of order n such that $\sum_{i=0}^{n}(-1)^{i}a_{i}\lambda^{n-i}$ and $\sum_{i=0}^{n}(-1)^{i}b_{i}\lambda^{n-i}$ are the characteristic polynomials of the signless Laplacian and the Laplacian matrices of G, respectively. We show that a i ?b i for i=0,1,?,n. As a consequence, we prove that for any ?, 0?1, if q 1,?,q n and μ 1,?,μ n are the signless Laplacian and the Laplacian eigenvalues of G, respectively, then $q_{1}^{\alpha}+\cdots+q_{n}^{\alpha}\geq\mu_{1}^{\alpha}+\cdots+\mu _{n}^{\alpha}$ .

The energy of a graph/matrix is the sum of the absolute values of its eigenvalues. We investigate the result of duplicating/removing an edge to the energy of a graph. We also deal with the problem that which graphs G have the property that if the edges of G are covered by some subgraphs, then the energy of G does not exceed the sum of the subgraphs’ energies. The problems are addressed in the general setting of energy of matrices which leads us to consider the singular values too. Among the other results it is shown that the energy of a complete multipartite graph increases if a new edge added or an old edge is deleted.

Let $G$ be a graph of order $n$ with signless Laplacian eigenvalues $q_1, \ldots,q_n$ and Laplacian eigenvalues $\mu_1,\ldots,\mu_n$. It is proved that for any real number $\alpha$ with $0 < \alpha\leq1$ or $2\leq\alpha < 3$, the inequality $q_1^\alpha+\cdots+ q_n^\alpha\geq \mu_1^\alpha+\cdots+\mu_n^\alpha$ holds, and for any real number $\beta$ with $1 < \beta < 2$, the inequality $q_1^\beta+\cdots+ q_n^\beta\le \mu_1^\beta+\cdots+\mu_n^\beta$ holds. In both inequalities, the equality is attained (for $\alpha \notin \{1,2\}$) if and only if $G$ is bipartite.