Search

The Seidel energy of a simple graph G is the sum of the absolute values of the eigenvalues of the Seidel matrix of G. In this paper we study the Seidel eigenvalues of complete multipartite graphs and find the exact value of the Seidel energy of the complete multipartite graphs.

Let G be a graph such that the color of its vertices is white or black. A dynamic vertex coloring for G is defined as follows. One starts with a certain set of black vertices. Then, at each time step, a black vertex with exactly one white neighbor forces its white neighbor to become black. The initial set of black vertices is called a zero forcing set if by iterating this process, all of the vertices of G become black. The zero forcing number of G (denoted by Z(G)) is the minimum cardinality of a zero forcing set in G. In this paper, we study the zero forcing number of trees. Let T be a tree with at least two vertices. We show that $$\Delta (T)-1\le Z(T)\le r(T)-1$$ , where $$\Delta (T)$$ and r(T) are the maximum degree and the number of pendant vertices of T, respectively. As a consequence, we obtain that $$Z(L(T))\ge Z(T)$$ , where L(T) is the line graph of T. We characterize all trees T such that $$Z(T)=\Delta (T)-1$$ . Finally, we study trees T with $$Z(T)= r(T)-1$$ .

For a simple graph G, the signless Laplacian matrix of G, denoted by Q ( G ) , is defined as D ( G ) + A ( G ) , where A ( G ) and D ( G ) are the adjacency matrix and the diagonal matrix of vertex...

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.

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.

A peacock graph $$PG=(i, j, k\,; b_1, b_2,\ldots ,b_s)$$, where $$i,j,k\ge 3$$ is a graph consisting of three cycles $$C_i$$, $$C_j$$, $$C_k$$ and $$s\,(\ge 1)$$ paths $$P_{b_1+1}, P_{b_2+1},\ldots , P_{b_s+1}$$ intersecting in a single vertex that all meet in one vertex. A graph G is said to be determined by the spectrum of its Laplacian matrix (DLS, for short) if every graph with the same Laplacian spectrum is isomorphic to G. If $$s=1$$, then the peacock graph is called clover graph. In Wang and Wang (Linear Multilinear Algebra 63(12):2396–2405, 2015), it was proved that all clover graphs are DLS. In this paper, we generalize this result and show that all peacock graphs are DLS.

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}}

Let $G$ be a graph with eigenvalues $lambda_1(G)geqcdotsgeqlambda_n(G)$. In this paper we find all simple graphs $G$ such that $G$ has at most twelve vertices and $G$ has exactly two non-negative eigenvalues. In other words we find all graphs $G$ on $n$ vertices such that $nleq12$ and $lambda_1(G)geq0$, $lambda_2(G)geq0$ and $lambda_3(G) 0$, $lambda_2(G)>0$ and $lambda_3(G)

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$?.

We consider a construction by which we obtain a simple graph $${\mathrm {Tr}}(H,v)$$ from a simple graph H and a non-isolated vertex v of H. We call this construction “Trung’s construction.” We prove that $${\mathrm {Tr}}(H,v)$$ is well covered, W $$_2$$ or Gorenstein if and only if H is so. Also, we present a formula for computing the independence polynomial of $${\mathrm {Tr}}(H,v)$$ and investigate when the independence complex of $${\mathrm {Tr}}(H,v)$$ satisfies the Charney–Davis conjecture. As a consequence of our results, we show that the independence complex of every Gorenstein planar graph with girth at least four satisfies the Charney–Davis conjecture.

Let $\alpha=\alpha(G)$ be the independence number of a simple graph $G$ with $n$ vertices and $I(G)$ be its edge ideal in $S=K[x_1,\ldots, x_n]$. If $S/I(G)$ is Gorenstein, the graph $G$ is called Gorenstein over $K$ and if $G$ is Gorenstein over every field, then we simply say that $G$ is Gorenstein. In this article, first we state a condition equivalent to $G$ being Gorenstein and using this we give a characterization of Gorenstein graphs with $\alpha=2$. Then we present some properties of Gorenstein graphs with $\alpha=3$ and as an application of these results we characterize triangle-free Gorenstein graphs with $\alpha=3$., Comment: 9 pages, 1 figure

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.

Richard Brualdi proposed in [Research problems from the Aveiro workshop on graph spectra, Linear Algebra Appl. 2007;423:172–181] the following problem: (Problem AWGS.4) Let and be two non-isomorphic graphs on n vertices with spectrarespectively. Define the distance between the spectra of and asDefine the cospectrality of byLetProblem AInvestigate for special classes of graphs. Problem BFind a good upper bound on . In this paper, we study Problem A and determine the cospectrality of all complete bipartite graphs by the Euclidian distance. More precisely, we show that for all positive integers m and n there are some positive integers r, s and a non-negative integer t such that , where is the complete bipartite graph with parts of sizes m and n.

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.

Let $G$ be a simple graph of order $n$. A dominating set of $G$ is a set $S$ of vertices of $G$ so that every vertex of $G$ is either in $S$ or adjacent to a vertex in $S$. The domination polynomial of $G$ is the polynomial $D(G,x)=\sum_{i=1}^{n} d(G,i) x^{i}$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$. In this paper we show that cycles are determined by their domination polynomials., Comment: To appear in Ars Combinatoria

A universal adjacency matrix of a graph $G$ with adjacency matrix $A$ is any matrix of the form $U = \alpha A + \beta I + \gamma J + \delta D$ with $\alpha \neq 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).