Search

If A(G) and D(G) are respectively the adjacency matrix and the diagonal matrix of vertex degrees of a connected graph G, the generalized adjacency matrix Aα(G) is defined as Aα(G) = α D(G) + (1 - α) A(G), where 0 ≤ α ≤ 1. The Aα (or generalized) spectral radius λ(Aα(G)) (or simply λα) is the largest eigenvalue of Aα(G). In this paper, we show that λα ≤ α Δ + (1 - α)√ 2m ( 1 - 1/ω), where m, Δ and ω = ω(G) are respectively the size, the largest degree and the clique number of G. Further, if G has order n, then we show that ... where di and mi are respectively the degree and the average 2-degree of the vertex Vi. [ABSTRACT FROM AUTHOR]

The multiple subdivision graph of a graph G , denoted by S n (G) , is the graph obtained by inserting n paths of length 2 replacing every edge of G. When n = 1 , S 1 (G) = S (G) is the subdivision graph of G. Let G 1 be a graph with n 1 vertices and m 1 edges, G 2 be a graph with n 2 vertices and m 2 edges. The quasi-corona SG-vertex join G 1 △ G 2 of G 1 and G 2 is the graph obtained from S (G 1) ∪ G 1 and n 1 copies of G 2 by joining every vertex of G 1 to every vertex of G 2 , and multiple SG-vertex join G 1 ⊙ G 2 is the graph obtained from S n (G 1) ∪ G 1 and G 2 by joining every vertex of G 1 to every vertex of G 2 . In this paper, we calculate analytic expression of characteristic polynomial of adjacency matrix of the above two types of joins of graphs for the case of G 1 being a regular graph. Then we obtain their adjacency spectra for the case of G 1 and G 2 being regular graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph with n vertices and m edges. Let W (G) = (G , w) be the weighted graph corresponding to G. Let λ 1 , λ 2 , ... , λ n be the eigenvalues of the adjacency matrix A (W (G)) of the weighted graph W (G). The energy E (W (G)) of a weighted graph W (G) is defined as the sum of absolute value of the eigenvalues of W (G). In this paper, we obtain upper bounds for the energy E (W (G)) , in terms of the sum of the squares of weights of the edges, the maximum weight, the maximum degree d 1 , the second maximum degree d 2 and the vertex covering number τ of the underlying graph G. As applications to these upper bounds we obtain some upper bounds for the energy (adjacency energy), the extended graph energy, the Randić energy and the signed energy of the connected graph G. We also obtain some new families of weighted graphs where the energy increases with increase in weights of the edges. [ABSTRACT FROM AUTHOR]

Let G = (V (G) , E (G)) be a simple graph with vertex set V (G) and edge set E (G) , c (G) = | E (G) | − | V (G) | + θ (G) be the dimension of cycle spaces of G with θ (G) the number of connected components of G , m (G) be the matching number of G , and η (G) be the nullity of G. It was shown in Wang and Wong (2014) that the nullity η (G) of G is bounded by an upper bound and a lower bound as | V (G) | − 2 m (G) − c (G) ≤ η (G) ≤ | V (G) | − 2 m (G) + 2 c (G). Graphs with nullity attaining the upper bound and the lower bound have been characterized by Song et al. (2015) and Wang (2016), respectively. In this paper, we prove that there is no graph with nullity η (G) = | V (G) | − 2 m (G) + 2 c (G) − 1. For fixed c (G) , infinitely many connected graphs with nullity | V (G) | − 2 m (G) + 2 c (G) − k , (0 ≤ k ≤ 3 c (G) , k ≠ 1) are also constructed. [ABSTRACT FROM AUTHOR]

A signed graph is a pair Γ = (G , σ) , where x = (V (G) , E (G)) is a graph and σ : E (G) → { + 1 , − 1 } is the sign function on the edges of G. For any α ∈ [ 0 , 1 ] we consider the matrix A α (Γ) = α D (G) + (1 − α) A (Γ) , where D (G) is the diagonal matrix of the vertex degrees of G , and A (Γ) is the adjacency matrix of Γ. Let m A α (Γ) (α) be the multiplicity of α as an A α (Γ) -eigenvalue, and let G have p (G) pendant vertices, q (G) quasi-pendant vertices, and no components isomorphic to K 2. It is proved that m A α (Γ) (α) = p (G) − q (G) whenever all internal vertices are quasi-pendant. If this is not the case, it turns out that m A α (Γ) (α) = p (G) − q (G) + m N α (Γ) (α) , where m N (Γ) (α) denotes the multiplicity of α as an eigenvalue of the matrix N α (Γ) obtained from A α (Γ) taking the entries corresponding to the internal vertices which are not quasi-pendant. Such results allow to state a formula for the multiplicity of 1 as an eigenvalue of the Laplacian matrix L (Γ) = D (G) − A (Γ). Furthermore, it is detected a class G of signed graphs whose nullity – i.e. the multiplicity of 0 as an A (Γ) -eigenvalue – does not depend on the chosen signature. The class G contains, among others, all signed trees and all signed lollipop graphs. It also turns out that for signed graphs belonging to a subclass G ′ ⊂ G the multiplicity of 1 as Laplacian eigenvalue does not depend on the chosen signatures. Such subclass contains trees and circular caterpillars. [ABSTRACT FROM AUTHOR]

Abstract A (1 , ≤ ℓ) -identifying code in digraph D is a dominating subset C of vertices of D , such that all distinct subsets of vertices of D with cardinality at most ℓ have distinct closed in-neighborhoods within C. As far as we know, it is the very first time that the spectral graph theory has been applied to the identifying codes. We give a new method to obtain an upper bound on ℓ for digraphs. The results obtained here can also be applied to graphs. [ABSTRACT FROM AUTHOR]

Abstract We investigate two Bruhat (partial) orders on graphs with vertices labeled 1 , 2 , ... , n and with a specified degree sequence R , equivalently, symmetric (0 , 1) -matrices with zero trace and a specified row sum vector R (adjacency matrices of such graphs). One is motivated by the classical Bruhat order on permutations while the other one, more restrictive, is defined by a switch of a pair of disjoint edges. In the Bruhat order, one seeks to concentrate the edges of a graph with a given degree sequence among the vertices with smallest labels, thereby producing a minimal graph in this order. We begin with a discussion of graphs whose isomorphism class does not change under a switch. Then we are interested in when the two Bruhat orders are identical. For labeled graphs of regular degree k , we show that the two orders are identical for k ≤ 2 but not for k = 3. [ABSTRACT FROM AUTHOR]

For a sequence of adjacency matrices, describing the unfolding of a network from the graph of a star, through graphs of a broom, to the graph of a link with constant vertices and edges, we show that the leading eigenvalue (the spectral radius) satisfies a simple algebraic equation. The equation allows easy numerical computation of the leading eigenvalue as well as a direct proof of its monotonicity in terms of the maximal degree of vertices. [ABSTRACT FROM AUTHOR]

In this paper we develop the concept of energy of a vertex introduced in Arizmendi and Juarez-Romero (2018). We derive basic inequalities, continuity properties, give examples and extend the definition to locally finite graphs. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) , V = { 1 , 2 , … , n } , be a simple connected graph with n vertices, m edges, and sequence of vertex degrees d 1  ≥  d 2  ≥ ⋅⋅⋅ ≥  d n  > 0, d i = d ( i ) . A large number of vertex–degree-based topological indices is of the form T I = T I ( G ) = ∑ i ∼ j F ( d i , d j ) , where F is pertinently chosen function with the property F ( x , y ) = F ( y , x ) . To each of such topological indices a corresponding adjacency matrix A = ( a i j ) , of order n  ×  n , can be associated. The trace of matrix A is denoted as t r ( A ) . For F ( d i , d j ) = 2 d i d j d i + d j , the geometric–arithmetic topological index, GA 1 , is obtained. Upper and lower bounds for GA 1 in terms of t r ( A 2 ) are determined. Also, we generalize a number of results reported in the literature and obtain some new bounds for the indices of the form TI . [ABSTRACT FROM AUTHOR]

Representing a subset of vertices in a graph by means of a matrix was introduced by E. Sampath Kumar. Let G(V, E) be a graph and S ⊆ V be a set of vertices. We can represent the set S by means of a matrix as follows, in the adjacency matrix A(G) of G replace the aii element by 1 if and only if, vi ∊ S. In this paper we study the set S being dominating set and corresponding domination energy of some class of graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected graph. Let 0 ≤ α ≤ 1 . Let A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) where D ( G ) and A ( G ) are the diagonal matrix of the vertex degrees of G and the adjacency matrix of G , respectively. Let p ( G ) > 0 and q ( G ) be the number of pendant vertices and quasi-pendant vertices of G , respectively. Let m G ( α ) be the multiplicity of α as an eigenvalue of A α ( G ) . It is proved that m G ( α ) ≥ p ( G ) − q ( G ) with equality if each internal vertex is a quasi-pendant vertex. If there is at least one internal vertex which is not a quasi-pendant vertex, the equality m G ( α ) = p ( G ) − q ( G ) + m N ( α ) is determined in which m N ( α ) is the multiplicity of α as an eigenvalue of the matrix N . This matrix is obtained from A α ( G ) taking the entries corresponding to the internal vertices which are non quasi-pendant vertices. These results are applied to search for the multiplicity of α as an eigenvalue of A α ( G ) when G is a path, a caterpillar, a circular caterpillar, a generalized Bethe tree or a Bethe tree. For the Bethe tree case, a simple formula for the nullity is given. [ABSTRACT FROM AUTHOR]

We give counterexamples to a result in F. Esser and F. Harary [2, Theorem 3] asserting that two nonisomorphic complete r -partite graphs with the same number of vertices have different spectral radii. We then derive some results on invariant factors and apply them to obtain relationship between the parameters of integral complete multipartite graphs and their integer eigenvalues. Necessary conditions for complete multipartite graphs to be integral are obtained. [ABSTRACT FROM AUTHOR]

Let be a finite-dimensional Hilbert space and be a finite frame for . For , we associate a simple graph denoted by and called frame graph, with all elements of as vertices, and two distinct vertices are adjacent when the inner product of them is nonzero. The associated graph is called a tight frame graph if the mentioned frame is tight. In this paper, we study some basic properties of and investigate the relation between the frame-theoretic properties of and the graph-theoretic properties of . For example, it is shown that trees on more than two vertices and cycles on more than five vertices are not tight frame graphs while complete graphs, complete graphs minus a single edge and the join of each graph with itself are tight frame graphs. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices, and let A ( G ) and D ( G ) denote respectively the adjacency matrix and the degree matrix of G . Define A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) for any real α ∈ [ 0 , 1 ] . The A α -characteristic polynomial of G is defined to be det ( x I n − A α ( G ) ) = ∑ j c α j ( G ) x n − j , where det ( ⁎ ) denotes the determinant of ⁎, and I n is the identity matrix of size n . The A α -spectrum of G consists of all roots of the A α -characteristic polynomial of G . A graph G is said to be determined by its A α -spectrum if all graphs having the same A α -spectrum as G are isomorphic to G . In this paper, we first formulate the first four coefficients c α 0 ( G ) , c α 1 ( G ) , c α 2 ( G ) and c α 3 ( G ) of the A α -characteristic polynomial of G . And then, we observe that A α -spectra are much efficient for us to distinguish graphs, by enumerating the A α -characteristic polynomials for all graphs on at most 10 vertices. To verify this observation, we characterize some graphs determined by their A α -spectra. [ABSTRACT FROM AUTHOR]

For an undirected simple graph G , the line graph L ( G ) is the graph whose vertex set is in one-to-one correspondence with the edge set of G where two vertices are adjacent if their corresponding edges in G have a common vertex. The energy E ( G ) is the sum of the absolute values of the eigenvalues of G . The vertex connectivity κ ( G ) is referred as the minimum number of vertices whose deletion disconnects G . The positive inertia ν + ( G ) corresponds to the number of positive eigenvalues of G . Finally, the matching number β ( G ) is the maximum number of independent edges of G . In this paper, we derive a sharp upper bound for the energy of the line graph of a graph G on n vertices having a vertex connectivity less than or equal to k . In addition, we obtain upper bounds on E ( G ) in terms of the edge connectivity, the inertia and the matching number of G . Moreover, a new family of hyperenergetic graphs is obtained. [ABSTRACT FROM AUTHOR]

Graph labeling where vertices and edges are assigned values subject to certain conditions have been motivated by various applied mathematical fields. Most of the problems in graph labeling are discussed on undirected graphs. Bloom G.S. and Hsu D.F. defined the labeling on directed graphs. In this paper, we discuss the adjacency matrices of graceful digraphs such as unidirectional paths, alternating paths, many orientations of directed star and a class of directed bistar. We also discuss the adjacency matrices of unidirectional paths and alternating paths if they are odd digraceful. [ABSTRACT FROM AUTHOR]

A signed graph G σ consists of an underlying graph G and a sign function σ , which assigns each edge uv of G a sign σ ( u v ) , either positive or negative. The adjacency matrix of G σ is defined as A ( G σ ) = ( a u , v σ ) with a u , v σ = σ ( u v ) a u , v , where a u , v = 1 if u , v ∈ V ( G ) are adjacent, and a u , v = 0 otherwise. The positive inertia index of G σ , written as p ( G σ ) , is defined to be the number of positive eigenvalues of A ( G σ ) . Recently, Yu et al. (2016) [12] characterized the signed graphs G σ with pendant vertices such that p ( G σ ) = 2 . In this paper, we extend the above work to a more general case, characterizing the signed graphs G σ with cut points whose positive inertia index is 2. [ABSTRACT FROM AUTHOR]

Let G [ F, V k , H v ] be the graph with k pockets, where F is a simple graph of order n  ≥ 1, V k = { v 1 , … , v k } is a subset of the vertex set of F and H v is a simple graph of order m  ≥ 2, v is a specified vertex of H v . Also let G [ F, E k , H uv ] be the graph with k edge-pockets, where F is a simple graph of order n  ≥ 2, E k = { e 1 , … , e k } is a subset of the edge set of F and H uv is a simple graph of order m  ≥ 3, uv is a specified edge of H uv such that H u v − u is isomorphic to H u v − v . In this paper, we obtain some results describing the signless Laplacian spectra of G [ F, V k , H v ] and G [ F, E k , H uv ] in terms of the signless Laplacian spectra of F, H v and F, H uv , respectively. In addition, we also give some results describing the adjacency spectrum of G [ F, V k , H v ] in terms of the adjacency spectra of F, H v . Finally, as many applications of these results, we construct infinitely many pairs of signless Laplacian (resp. adjacency) cospectral graphs. [ABSTRACT FROM AUTHOR]

In a certain class of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum. A connected graph containing two or three cycles is called a bicyclic graph if its number of edges is equal to its number of vertices plus one. In this paper, we characterize the minimizing graph among all the connected graphs that belong to a class of graphs whose complements are bicyclic with two cycles. [ABSTRACT FROM AUTHOR]

We construct a graph-theoretic model for Jacobsthal and Jacobsthal-Lucas numbers. As byproducts, we then develop addition formulas for the Jacobsthal family. [ABSTRACT FROM AUTHOR]

We consider only connected bipartite graphs G with a unique perfect matching M . Let G w be the weighted graph obtained from G by giving weights to its edges using the positive weight function w : E ( G ) → ( 0 , ∞ ) such that w ( e ) = 1 for each e ∈ M . An unweighted graph G may be viewed as a weighted graph with the weight function w ≡ 1 . A weighted graph G w is nonsingular if its adjacency matrix A ( G w ) is nonsingular. The inverse of a nonsingular weighted graph G w is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G w ) via a diagonal matrix of ±1s. By G / M we denote the graph obtained from G by contracting each edge of M to a single vertex. It is known that if G / M is bipartite, then G w is invertible for each weight function w. In this article, we consider the converse of this result and show that if G w is invertible for each w, then the graph G / M is bipartite. We also supply exact conditions under which G w is invertible for one w will force that the graph G / M is bipartite. [ABSTRACT FROM AUTHOR]

Graphs G and H are called cospectral if they have the same characteristic polynomial. If eigenvalues are integral, then corresponding graphs are called integral graph. In this article we introduce a construction to produce pairs of cospectral integral regular graphs. Generalizing the construction of G4(a, b) and G5(a, b) due to Wang and Sun, we define graphs G4(G,H) and G5(G,H) and show that they are cospectral integral regular when G is an integral q- regular graph of order m and H is an integral q-regular graph of order (b -- 2)m for some integer b ≥3. [ABSTRACT FROM AUTHOR]

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices [ABSTRACT FROM AUTHOR]

Let G be a g√aph on n ve√tices and G its complement. In this pape√, we p√ove a No√dhaus-Gaddum type inequality to the second la√gest eigenvalue of a g√aph G, λ2(G), λ2(G) + λ2(G) ≤ -1 + √ n2/2 - n + 1; when G is a g√aph with gi√th at least 5. Also, we show that the bound above is tight. Besides, we p√ove that this √esult holds fo√ some classes of connected g√aphs such as t√ees, k-cyclic, √egula√ bipa√tite and complete multipa√tite g√aphs. Based on these facts, we conjectu√e that ou√ √esult holds to any g√aph. [ABSTRACT FROM AUTHOR]

A Hamiltonian cycle in a graph is a cycle that visits each node/vertex exactly once. A graph containing a Hamiltonian cycle is called a Hamiltonian graph. There have been several researches to find the number of Hamiltonian cycles of a Hamilton graph. As the number of vertices and edges grow, it becomes very difficult to keep track of all the different ways through which the vertices are connected. Hence, analysis of large graphs can be efficiently done with the assistance of a computer system that interprets graphs as matrices. And, of course, a good and well written algorithm will expedite the analysis even faster. The most convenient way to quickly test whether there is an edge between two vertices is to represent graphs using adjacent matrices. In this paper, a new algorithm is proposed to find fuzzy Hamiltonian cycle using adjacency matrix and the degree of the vertices of a fuzzy graph. A fuzzy graph structure is also modeled to illustrate the proposed algorithms with the selected air network of Indigo airlines. [ABSTRACT FROM AUTHOR]

The k-th power of a graph G, denoted by [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V(G) = {v1,v2,..., vn}. Let A(G) be the adjacency matrix of a graph G. The rows of A(G) corresponding to a vertex v of G, denoted by s(v) is the string. The Hamming index of a graph G is the sum of the Hamming distances between all pairs of vertices of G. In this paper we obtain Hamming index generated by adjacency matrix of some thorn graphs. [ABSTRACT FROM AUTHOR]

A digraph Γ = ( V , E ) is a line digraph when every pair of vertices u , v ∈ V have either equal or disjoint in-neighborhoods. When this condition only applies for vertices in a given subset (with at least two elements), we say that Γ is a locally line digraph. In this paper we give a new method to obtain a digraph Γ ′ cospectral with a given locally line digraph Γ with diameter D , where the diameter D ′ of Γ ′ is in the interval [ D − 1 , D + 1 ] . In particular, when the method is applied to De Bruijn or Kautz digraphs, we obtain cospectral digraphs with the same algebraic properties that characterize the formers. [ABSTRACT FROM AUTHOR]

Given a graph G . The fewest number of vertices whose deletion yields a bipartite graph from G was defined by S. Fallat and Yi-Zheng Fan to be the vertex bipartiteness of G and it is denoted by υ b ( G ) . We consider the set Σ k ( n ) defined by { G = ( V ( G ) , E ( G ) ) : G connected , | V ( G ) | = n and υ b ( G ) ≤ k } . In this work we identify the graph in Σ k ( n ) with maximum spectral radius and maximum signless Laplacian spectral radius. [ABSTRACT FROM AUTHOR]

Let hom(G, H) denote the number of homomorphisms from a graph G to a graph H. In this paper we study the number of homomorphisms of trees into a path, and prove that hom(Pm, Pn) ≤ hom(Tm, Pn) ≤ hom(Sm, Pn), where Tm is any tree on m vertices, and Pm and Sm denote the path and star on m vertices, respectively. This completes the study of extremal problems concerning the number of homomorphisms between trees started in the paper Graph Homomorphisms Between Trees [Electron. J. Combin., 21 (2014), 4.9] written by the authors of the current paper. [ABSTRACT FROM AUTHOR]

A complete caterpillar is a caterpillar in which each internal vertex is a quasi-pendent vertex. In this paper, in the class of all complete caterpillars on n vertices and diameter d, the caterpillar attaining the largest Laplacian index is determined. In addition, it is proved that this caterpillar also attains the largest adjacency index. [ABSTRACT FROM AUTHOR]

Let k , p , q be positive integers with k < p < q + 1 . We prove that the maximum spectral radius of a simple bipartite graph obtained from the complete bipartite graph K p , q of bipartition orders p and q by deleting k edges is attained when the deleted edges are all incident on a common vertex which is located in the partite set of order q . Our method is based on new sharp upper bounds on the spectral radius of bipartite graphs in terms of their degree sequences. [ABSTRACT FROM AUTHOR]