70 results on '"Adjacency matrix"'
Search Results
2. Walks and eigenvalues of signed graphs
- Author
-
Stanić Zoran
- Subjects
adjacency matrix ,eigenvalue ,walk ,spectral radius ,negative cycle ,05c50 ,05c22 ,Mathematics ,QA1-939 - Abstract
In this article, we consider the relationships between walks in a signed graph G˙\dot{G} and its eigenvalues, with a particular focus on the largest absolute value of its eigenvalues ρ(G˙)\rho \left(\dot{G}), known as the spectral radius. Among other results, we derive a sequence of lower bounds for ρ(G˙)\rho \left(\dot{G}) expressed in terms of walks or closed walks. We also prove that ρ(G˙)\rho \left(\dot{G}) attains the spectral radius of the underlying graph GG if and only if G˙\dot{G} is switching equivalent to GG or its negation. It is proved that the length kk of the shortest negative cycle in G˙\dot{G} and the number of such cycles are determined by the spectrum of G˙\dot{G} and the spectrum of GG. Finally, a relation between kk and characteristic polynomials of G˙\dot{G} and GG is established.
- Published
- 2023
- Full Text
- View/download PDF
3. On spectral spread and trace norm of Sombor matrix
- Author
-
Rather, Bilal Ahmad, Imran, Muhammad, and Diene, Adama
- Published
- 2024
- Full Text
- View/download PDF
4. On inverse sum indeg energy of graphs
- Author
-
Jamal Fareeha, Imran Muhammad, and Rather Bilal Ahmad
- Subjects
topological indices ,adjacency matrix ,inverse sum indeg matrix ,energy ,05c50 ,05c09 ,05c92 ,15a18 ,Mathematics ,QA1-939 - Abstract
For a simple graph with vertex set {v1,v2,…,vn}\left\{{v}_{1},{v}_{2},\ldots ,{v}_{n}\right\} and degree sequence dvii=1,2,…,n{d}_{{v}_{i}}\hspace{0.33em}i=1,2,\ldots ,n, the inverse sum indeg matrix (ISI matrix) AISI(G)=(aij){A}_{{\rm{ISI}}}\left(G)=\left({a}_{ij}) of GG is a square matrix of order n,n, where aij=dvidvjdvi+dvj,{a}_{ij}=\frac{{d}_{{v}_{i}}{d}_{{v}_{j}}}{{d}_{{v}_{i}}+{d}_{{v}_{j}}}, if vi{v}_{i} is adjacent to vj{v}_{j} and 0, otherwise. The multiset of eigenvalues τ1≥τ2≥⋯≥τn{\tau }_{1}\ge {\tau }_{2}\hspace{0.33em}\ge \cdots \ge {\tau }_{n} of AISI(G){A}_{{\rm{ISI}}}\left(G) is known as the ISI spectrum of GG. The ISI energy of GG is the sum ∑i=1n∣τi∣\mathop{\sum }\limits_{i=1}^{n}| {\tau }_{i}| of the absolute ISI eigenvalues of G.G. In this article, we give some properties of the ISI eigenvalues of graphs. Also, we obtain the bounds of the ISI eigenvalues and characterize the extremal graphs. Furthermore, we construct pairs of ISI equienergetic graphs for each n≥9n\ge 9.
- Published
- 2023
- Full Text
- View/download PDF
5. More on Signed Graphs with at Most Three Eigenvalues
- Author
-
Ramezani Farzaneh, Rowlinson Peter, and Stanić Zoran
- Subjects
adjacency matrix ,simple eigenvalue ,strongly regular signed graph ,vertex-deleted subgraph ,weighing matrix ,association scheme ,05c22 ,05c50 ,Mathematics ,QA1-939 - Abstract
We consider signed graphs with just 2 or 3 distinct eigenvalues, in particular (i) those with at least one simple eigenvalue, and (ii) those with vertex-deleted subgraphs which themselves have at most 3 distinct eigenvalues. We also construct new examples using weighing matrices and symmetric 3-class association schemes.
- Published
- 2022
- Full Text
- View/download PDF
6. On the spread of the geometric-arithmetic matrix of graphs
- Author
-
Bilal A. Rather, M. Aouchiche, and S. Pirzada
- Subjects
Adjacency matrix ,spectral radius ,geometric-arithmetic index ,geometric-arithmetic spectrum ,spread ,05C50 ,Mathematics ,QA1-939 - Abstract
In a graph G, if di is the degree of a vertex vi, the geometric-arithmetic matrix GA(G) is a square matrix whose [Formula: see text]-th entry is [Formula: see text] whenever vertices i and j are adjacent and 0 otherwise. The set of all eigenvalues of GA(G) including multiplicities is known as the geometric-arithmetic spectrum of G. The difference between the largest and the smallest geometric-arithmetic eigenvalue is called the geometric-arithmetic spread [Formula: see text] of G. In this article, we investigate some properties of [Formula: see text] We obtain lower and upper bounds of [Formula: see text] and show the existence of graphs for which equality holds. Further, [Formula: see text] is computed for various graph operations.
- Published
- 2022
- Full Text
- View/download PDF
7. Signed graphs with at most three eigenvalues.
- Author
-
Ramezani, Farzaneh, Rowlinson, Peter, and Stanić, Zoran
- Abstract
We investigate signed graphs with just 2 or 3 distinct eigenvalues, mostly in the context of vertex-deleted subgraphs, the join of two signed graphs or association schemes. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
8. Corrigendum to 'Achievable Multiplicity partitions in the Inverse Eigenvalue Problem of a graph' [Spec. Matrices 2019; 7:276-290.]
- Author
-
Adm Mohammad, Fallat Shaun, Meagher Karen, Nasserasr Shahla, Plosker Sarah, and Yang Boting
- Subjects
inverse eigenvalue problem ,multiplicity partition ,adjacency matrix ,minimum rank ,distinct eigenvalues ,graphs ,05c50 ,15a18 ,Mathematics ,QA1-939 - Abstract
We correct an error in the original Lemma 3.4 in our paper “Achievable Multiplicity partitions in the IEVP of a graph”’ [Spec. Matrices 2019; 7:276-290.]. We have re-written Section 3 accordingly.
- Published
- 2020
- Full Text
- View/download PDF
9. On Regular Signed Graphs with Three Eigenvalues
- Author
-
Anđelić Milica, Koledin Tamara, and Stanić Zoran
- Subjects
adjacency matrix ,eigenvalue ,regular signed graph ,signed line graph ,block design ,05c50 ,05c22 ,65f15 ,Mathematics ,QA1-939 - Abstract
In this paper our focus is on regular signed graphs with exactly 3 (distinct) eigenvalues. We establish certain basic results; for example, we show that they are walk-regular. We also give some constructions and determine all the signed graphs with 3 eigenvalues, under the constraint that they are either signed line graphs or have vertex degree 3. We also report our result of computer search on those with at most 10 vertices.
- Published
- 2020
- Full Text
- View/download PDF
10. Some Observations on the Smallest Adjacency Eigenvalue of a Graph
- Author
-
Cioabă Sebastian M., Elzinga Randall J., and Gregory David A.
- Subjects
graph spectrum ,smallest eigenvalue ,adjacency matrix ,graph decomposition ,clique partition ,claw-free graphs ,maximum cut ,05c50 ,05c75 ,05c76 ,05e30 ,15a18 ,Mathematics ,QA1-939 - Abstract
In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds.
- Published
- 2020
- Full Text
- View/download PDF
11. Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
- Author
-
Adm Mohammad, Fallat Shaun, Meagher Karen, Nasserasr Shahla, Plosker Sarah, and Yang Boting
- Subjects
inverse eigenvalue problem ,multiplicity partition ,adjacency matrix ,minimum rank ,distinct eigenvalues ,graphs ,05c50 ,15a18 ,Mathematics ,QA1-939 - Abstract
Associated to a graph G is a set 𝒮(G) of all real-valued symmetric matrices whose off-diagonal entries are nonzero precisely when the corresponding vertices of the graph are adjacent, and the diagonal entries are free to be chosen. If G has n vertices, then the multiplicities of the eigenvalues of any matrix in 𝒮 (G) partition n; this is called a multiplicity partition.
- Published
- 2019
- Full Text
- View/download PDF
12. Least eigenvalue of the connected graphs whose complements are cacti
- Author
-
Wang Haiying, Javaid Muhammad, Akram Sana, Jamal Muhammad, and Wang Shaohui
- Subjects
adjacency matrix ,least eigenvalue ,connected graphs ,cacti ,15a18 ,05c50 ,05c40 ,05d05 ,Mathematics ,QA1-939 - Abstract
Suppose that Γ is a graph of order n and A(Γ) = [ai,j] is its adjacency matrix such that ai,j is equal to 1 if vi is adjacent to vj and ai,j is zero otherwise, where 1 ≤ i, j ≤ n. In a family of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix is minimum in the set of the least eigenvalues of all the graphs. Petrović et al. [On the least eigenvalue of cacti, Linear Algebra Appl., 2011, 435, 2357-2364] characterized a minimizing graph in the family of all cacti such that the complement of this minimizing graph is disconnected. In this paper, we characterize the minimizing graphs G ∈ Ωnc$\begin{array}{} {\it\Omega}^c_n \end{array}$, i.e.
- Published
- 2019
- Full Text
- View/download PDF
13. A note on a walk-based inequality for the index of a signed graph
- Author
-
Stanić Zoran
- Subjects
signed graph ,walk ,adjacency matrix ,index ,upper bound ,05c22 ,05c50 ,Mathematics ,QA1-939 - Abstract
We derive an inequality that includes the largest eigenvalue of the adjacency matrix and walks of an arbitrary length of a signed graph. We also consider certain particular cases.
- Published
- 2021
- Full Text
- View/download PDF
14. Eigenvalue Bounds for Some Classes of Matrices Associated with Graphs.
- Author
-
Mehatari, Ranjit and Kannan, M. Rajesh
- Abstract
For a given complex square matrix A with constant row sum, we establish two new eigenvalue inclusion sets. Using these bounds, first, we derive bounds for the second largest and the smallest eigenvalues of adjacency matrices of fc-regular graphs. Then we establish some bounds for the second largest and the smallest eigenvalues of the normalized adjacency matrices of graphs and the second smallest and the largest eigenvalues of the Laplacian matrices of graphs. The sharpness of these bounds is verified by examples. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
15. Main Eigenvalues of Real Symmetric Matrices with Application to Signed Graphs.
- Author
-
Stanić, Zoran
- Abstract
An eigenvalue of a real symmetric matrix is called main if there is an associated eigenvector not orthogonal to the all-1 vector j. Main eigenvalues are frequently considered in the framework of simple undirected graphs. In this study we generalize some results and then apply them to signed graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
16. Commuting decomposition of Kn1,n2,...,nk through realization of the product A(G)A(GPk )
- Author
-
Bhat K. Arathi and Sudhakara G.
- Subjects
adjacency matrix ,k-complement ,graphical ,matrix product ,commutativity ,commuting decomposition ,05c50 ,15a24 ,Mathematics ,QA1-939 - Abstract
In this paper, we introduce the notion of perfect matching property for a k-partition of vertex set of given graph. We consider nontrivial graphs G and GPk , the k-complement of graph G with respect to a kpartition of V(G), to prove that A(G)A(GPk ) is realizable as a graph if and only if P satis_es perfect matching property. For A(G)A(GPk ) = A(Γ) for some graph Γ, we obtain graph parameters such as chromatic number, domination number etc., for those graphs and characterization of P is given for which GPk and Γ are isomorphic. Given a 1-factor graph G with 2n vertices, we propose a partition P for which GPk is a graph of rank r and A(G)A(GPk ) is graphical, where n ≤ r ≤ 2n. Motivated by the result of characterizing decomposable Kn,n into commuting perfect matchings [2], we characterize complete k-partite graph Kn1,n2,...,nk which has a commuting decomposition into a perfect matching and its k-complement.
- Published
- 2018
- Full Text
- View/download PDF
17. Construction of Cospectral Integral Regular Graphs
- Author
-
Bapat Ravindra B. and Karimi Masoud
- Subjects
eigenvalue ,cospectral graphs ,adjacency matrix ,integral graphs ,05c50 ,Mathematics ,QA1-939 - Abstract
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 𝒢4(G,H) and 𝒢5(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.
- Published
- 2017
- Full Text
- View/download PDF
18. Energy of a vertex.
- Author
-
Arizmendi, Octavio, Fernandez Hidalgo, Jorge, and Juarez-Romero, Oliver
- Subjects
- *
MATHEMATICAL equivalence , *CONTINUITY , *GRAPH theory , *GEOMETRIC vertices , *SPECTRAL geometry , *FINITE groups - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
19. Spectral characterizations of anti-regular graphs.
- Author
-
Aguilar, Cesar O., Lee, Joon-yeob, Piato, Eric, and Schweitzer, Barbara J.
- Subjects
- *
REGULAR graphs , *CHEBYSHEV polynomials , *EIGENVALUES , *GRAPH theory , *MATRICES (Mathematics) , *ASYMPTOTIC distribution - Abstract
We study the eigenvalues of the unique connected anti-regular graph A n . Using Chebyshev polynomials of the second kind, we obtain a trigonometric equation whose roots are the eigenvalues and perform elementary analysis to obtain an almost complete characterization of the eigenvalues. In particular, we show that the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] contains only the trivial eigenvalues λ = − 1 or λ = 0 , and any closed interval strictly larger than Ω will contain eigenvalues of A n for all n sufficiently large. We also obtain bounds for the maximum and minimum eigenvalues, and for all other eigenvalues we obtain interval bounds that improve as n increases. Moreover, our approach reveals a more complete picture of the bipartite character of the eigenvalues of A n , namely, as n increases the eigenvalues are (approximately) symmetric about the number − 1 2 . We also obtain an asymptotic distribution of the eigenvalues as n → ∞ . Finally, the relationship between the eigenvalues of A n and the eigenvalues of a general threshold graph is discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
20. A characterization of oriented hypergraphic Laplacian and adjacency matrix coefficients.
- Author
-
Chen, Gina, Liu, Vivian, Robinson, Ellen, Rusnak, Lucas J., and Wang, Kyle
- Subjects
- *
HYPERGRAPHS , *LAPLACIAN matrices , *COEFFICIENTS (Statistics) , *MATHEMATICAL bounds , *GENERALIZATION - Abstract
An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
21. On the multiplicity of α as an eigenvalue of Aα(G) of graphs with pendant vertices.
- Author
-
Cardoso, Domingos M., Pastén, Germain, and Rojo, Oscar
- Subjects
- *
EIGENVALUES , *MULTIPLICITY (Mathematics) , *GEOMETRIC vertices , *SET theory , *EIGENANALYSIS - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
22. On the α-index of graphs with pendent paths.
- Author
-
Nikiforov, Vladimir and Rojo, Oscar
- Subjects
- *
GRAPH theory , *LINEAR algebra , *LAPLACIAN operator , *MATRICES (Mathematics) , *LAPLACIAN matrices - Abstract
Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . This paper presents some extremal results about the spectral radius ρ α ( G ) of A α ( G ) that generalize previous results about ρ 0 ( G ) and ρ 1 / 2 ( G ) . In particular, write B p , q , r be the graph obtained from a complete graph K p by deleting an edge and attaching paths P q and P r to its ends. It is shown that if α ∈ [ 0 , 1 ) and G is a graph of order n and diameter at least k , then ρ α ( G ) ≤ ρ α ( B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ ) , with equality holding if and only if G = B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ . This result generalizes results of Hansen and Stevanović [5] , and Liu and Lu [7] . [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
23. On the Aα-spectral radius of a graph.
- Author
-
Xue, Jie, Lin, Huiqiu, Liu, Shuting, and Shu, Jinlong
- Subjects
- *
GRAPH theory , *GRAPHIC methods , *MATRICES (Mathematics) , *COMPLEX matrices , *LINEAR algebra - Abstract
Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For any real α ∈ [ 0 , 1 ] , Nikiforov [3] defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . The largest eigenvalue of A α ( G ) is called the A α -spectral radius of G . In this paper, we give three edge graft transformations on A α -spectral radius. As applications, we determine the unique graph with maximum A α -spectral radius among all connected graphs with diameter d , and determine the unique graph with minimum A α -spectral radius among all connected graphs with given clique number. In addition, some bounds on the A α -spectral radius are obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
24. Integral complete multipartite graphs.
- Author
-
Bapat, Ravindra B. and Karimi, Masoud
- Subjects
- *
GEOMETRIC vertices , *INVARIANTS (Mathematics) , *GRAPHIC methods , *FINITE fields , *MATHEMATICS theorems , *MATHEMATICAL models - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
25. On the Aα-characteristic polynomial of a graph.
- Author
-
Liu, Xiaogang and Liu, Shunyi
- Subjects
- *
POLYNOMIALS , *GRAPH theory , *GEOMETRIC vertices , *COEFFICIENTS (Statistics) - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
26. On line graphs with maximum energy.
- Author
-
Lenes, Eber, Mallea-Zepeda, Exequiel, Robbiano, María, and Rodríguez Z., Jonnathan
- Subjects
- *
GEOMETRIC vertices , *GRAPHIC methods , *EIGENVALUES , *MATHEMATICAL bounds , *MATRICES (Mathematics) - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
27. Signed graphs with cut points whose positive inertia indexes are two.
- Author
-
Wang, Xinlei, Wong, Dein, and Tian, Fenglei
- Subjects
- *
LINEAR algebra , *GEOMETRIC vertices , *GRAPH theory , *LAPLACIAN matrices , *GRAPHIC methods - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
28. Unicyclic graphs with bicyclic inverses.
- Author
-
Panda, Swarup
- Abstract
A graph is nonsingular if its adjacency matrix A( G) is nonsingular. The inverse of a nonsingular graph G is a graph whose adjacency matrix is similar to A( G) via a particular type of similarity. Let H denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in H which possess unicyclic inverses. We present a characterization of unicyclic graphs in H which possess bicyclic inverses. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
29. Inverses of weighted graphs.
- Author
-
Panda, S.K. and Pati, S.
- Subjects
- *
WEIGHTED graphs , *INVERSE relationships (Mathematics) , *BIPARTITE graphs , *MATRICES (Mathematics) , *GEOMETRIC vertices - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
30. The spectra of subKautz and cyclic Kautz digraphs.
- Author
-
Dalfó, C.
- Subjects
- *
DIRECTED graphs , *GRAPH theory , *POLYNOMIALS , *INTEGERS , *MATHEMATICAL models - Abstract
Kautz digraphs K ( d , ℓ ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz C K ( d , ℓ ) and the subKautz s K ( d , 2 ) digraphs were recently introduced by Böhmová, Huemer and the author. In this paper we propose a new method to obtain the complete spectra of subKautz s K ( d , 2 ) and cyclic Kautz C K ( d , 3 ) digraphs, for all d ≥ 3 , through the Hoffman–McAndrew polynomial and regular partitions. This approach can be useful to find the spectra of other families of digraphs with high regularity. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
31. Self-inverse unicyclic graphs and strong reciprocal eigenvalue property.
- Author
-
Bapat, R.B., Panda, S.K., and Pati, S.
- Subjects
- *
GRAPH theory , *MATRICES (Mathematics) , *SINGULAR integrals , *ISOMORPHISM (Mathematics) , *EIGENVALUES - Abstract
We consider only simple graphs. A graph G is said to be nonsingular if its adjacency matrix A ( G ) is nonsingular. The inverse of a nonsingular graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G ) via a diagonal matrix of ±1s. An invertible graph G is said to be a self-inverse graph if G is isomorphic to its inverse. Let H be the class of connected bipartite graphs with unique perfect matchings. We consider the problem of characterizing the graphs in H which are self-inverse graphs. In this article, we answer this problem for the class of unicyclic graphs. The study of the strong reciprocal eigenvalue property is closely related to the study of graphs which are isomorphic to their inverse graphs. A nonsingular graph G is said to satisfy the property (SR) if the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) and they both have the same multiplicities. In this article, we show that if a unicyclic graph G in H has property (SR), then G is invertible and the inverse graph of G is unicyclic. As an application, we show that a noncorona unicyclic graph in H with property (SR) can have one of the five specified structures. Finally, our discussions lead to the following problem. Does there exist a unicyclic graph G ∈ H which has property (SR) but G is not self-inverse? [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
32. On some graphs which satisfy reciprocal eigenvalue properties.
- Author
-
Panda, S.K. and Pati, S.
- Subjects
- *
GRAPH theory , *EIGENVALUES , *BIPARTITE graphs , *MATRICES (Mathematics) , *VERTEX operator algebras - Abstract
We consider only simple graphs. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. On the class H g of such graphs G the equivalence of the following statements are known. i) The reciprocal of the spectral radius of the adjacency matrix A ( G ) is the least positive eigenvalue of the adjacency matrix. ii) The graph is isomorphic to its inverse, where the inverse of a graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G ) via a diagonal matrix of ±1s. iii) The graph has the reciprocal eigenvalue property, that is, the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) . iv) The graph has the strong reciprocal eigenvalue property, that is, the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) and they both have the same multiplicities. v) The graph is a corona graph, that is, it is obtained by taking a bipartite graph and then by inserting a new adjacent vertex of degree one at each vertex. It is known that the statements iii) and iv) are not equivalent, if we allow nonbipartite graphs. However, the equivalence of these two is not yet known for the class of bipartite graphs with unique perfect matchings, where we relax the condition of bipartiteness of the contracted graph. In this article, we establish the equivalence of the first four statements for a class larger than H g . We then supply a constructive structural description of those graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
33. Spectral radius of uniform hypergraphs.
- Author
-
Lin, Hongying and Zhou, Bo
- Subjects
- *
UNIFORM algebras , *HYPERGRAPHS , *MATHEMATICAL proofs , *TREE graphs , *MATRICES (Mathematics) - Abstract
We prove a result concerning the behavior of the spectral radius of a hypergraph under relocations of edges. We determine the unique hypergraphs with maximum spectral radius among connected k -uniform hypergraphs with fixed number of pendant edges, the unique k -uniform hypertrees with respectively maximum, second maximum and third maximum spectral radius, the unique k -uniform unicyclic hypergraphs ( k -uniform linear unicyclic hypergraphs, respectively) with respectively maximum and second maximum spectral radius. We also determine the unique hypergraphs with maximum spectral radius among k -uniform unicyclic hypergraphs with given girth. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
34. The graphs with all but two eigenvalues equal to $$-2$$ or 0.
- Author
-
Cioabă, Sebastian, Haemers, Willem, and Vermette, Jason
- Subjects
EIGENVALUES ,GRAPHIC methods ,EIGENVECTORS ,GRAPH theory ,PARALLEL algorithms - Abstract
We determine all graphs for which the adjacency matrix has at most two eigenvalues (multiplicities included) not equal to $$-2$$ , or 0, and determine which of these graphs are determined by their adjacency spectrum. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
35. On the nullity number of graphs.
- Author
-
Aouchiche, Mustapha and Hansen, Pierre
- Subjects
DOMINATING set ,MODULES (Algebra) ,SUBGRAPHS ,SUBSET selection ,GEOMETRIC vertices - Abstract
The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60-67] that η ≤ n-D, where η, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
36. On the Aα-spectra of trees.
- Author
-
Nikiforov, Vladimir, Pastén, Germain, Rojo, Oscar, and Soto, Ricardo L.
- Subjects
- *
TREE graphs , *MATHEMATICAL inequalities , *MATRICES (Mathematics) , *MATHEMATICAL bounds , *TOPOLOGY - Abstract
Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , define the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . This paper gives several results about the A α -matrices of trees. In particular, it is shown that if T Δ is a tree of maximal degree Δ, then the spectral radius of A α ( T Δ ) satisfies the tight inequality ρ ( A α ( T Δ ) ) < α Δ + 2 ( 1 − α ) Δ − 1 , which implies previous bounds of Godsil, Lovász, and Stevanović. The proof is deduced from some new results about the A α -matrices of Bethe trees and generalized Bethe trees. In addition, several bounds on the spectral radius of A α of general graphs are proved, implying tight bounds for paths and Bethe trees. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
37. A note on the positive semidefiniteness of Aα(G).
- Author
-
Nikiforov, Vladimir and Rojo, Oscar
- Subjects
- *
SEMIDEFINITE programming , *GRAPH theory , *EIGENVALUES , *BIPARTITE graphs , *LAPLACIAN matrices - Abstract
Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . Let α 0 ( G ) be the smallest α for which A α ( G ) is positive semidefinite. It is known that α 0 ( G ) ≤ 1 / 2 . The main results of this paper are: (1) if G is d -regular then α 0 = − λ min ( A ( G ) ) d − λ min ( A ( G ) ) , where λ min ( A ( G ) ) is the smallest eigenvalue of A ( G ) ; (2) G contains a bipartite component if and only if α 0 ( G ) = 1 / 2 ; (3) if G is r -colorable, then α 0 ( G ) ≥ 1 / r . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
38. On the addition of squares of units modulo n.
- Author
-
Mollahajiaghaei, Mohsen
- Subjects
- *
BRAUER groups , *MATHEMATICAL proofs , *GENERALIZATION , *RESIDUE theorem , *RING theory - Abstract
Let Z n be the ring of residue classes modulo n , and let Z n ⁎ be the group of its units. 90 years ago, Brauer obtained a formula for the number of representations of c ∈ Z n as the sum of k units. Recently, Yang and Tang (2015) [6] gave a formula for the number of solutions of the equation x 1 2 + x 2 2 = c with x 1 , x 2 ∈ Z n ⁎ . In this paper, we generalize this result. We find an explicit formula for the number of solutions of the equation x 1 2 + ⋯ + x k 2 = c with x 1 , … , x k ∈ Z n ⁎ . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
39. Strong reciprocal eigenvalue property of a class of weighted graphs.
- Author
-
Bapat, R.B., Panda, S.K., and Pati, S.
- Subjects
- *
EIGENVALUES , *SET theory , *WEIGHTED graphs , *UNIQUENESS (Mathematics) , *MATRICES (Mathematics) - Abstract
Let H be the class of connected bipartite graphs G with a unique perfect matching M . For G ∈ H , let W G be the set of weight functions w on the edge set E ( G ) such that w ( e ) = 1 for each matching edge and w ( e ) > 0 for each nonmatching edge. Let G w denote the weighted graph with G ∈ H and w ∈ W G . The graph G w is said to satisfy the reciprocal eigenvalue property, property (R) , if 1 / λ is an eigenvalue of the adjacency matrix A ( G w ) whenever λ is an eigenvalue of A ( G w ) . Moreover, if the multiplicities of the reciprocal eigenvalues are the same, we say G w has the strong reciprocal eigenvalue property, property (SR) . Let H g = { G ∈ H | G / M is bipartite } , where G / M is the graph obtained from G by contracting each edge in M to a vertex. Recently in [12] , it was shown that if G ∈ H g , then G w has property (SR) for some w ∈ W G if and only if G w has property (SR) for each w ∈ W G if and only if G is a corona graph (obtained from another graph H by adding a new pendant vertex to each vertex of H ). Now we have the following questions. Is there a graph G ∈ H ∖ H g such that G w has property (SR) for each w ∈ W G ? Are there graphs G ∈ H ∖ H g such that G w never has property (SR), not even for one w ∈ W G ? Are there graphs G ∈ H such that G w has property (SR) for some w ∈ W G but not for all w ∈ W G ? In this article, we supply answers to these three questions. We also supply a graph class larger than H g where for any graph G , if G w has property (SR) for one w ∈ W G , then G is a corona graph. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
40. Conjectured bounds for the sum of squares of positive eigenvalues of a graph.
- Author
-
Elphick, Clive, Farber, Miriam, Goldberg, Felix, and Wocjan, Pawel
- Subjects
- *
SUM of squares , *EIGENVALUES , *GRAPHIC methods , *MATHEMATICAL bounds , *LOGICAL prediction - Abstract
A well known upper bound for the spectral radius of a graph, due to Hong, is that μ 1 2 ≤ 2 m − n + 1 if δ ≥ 1 . It is conjectured that for connected graphs n − 1 ≤ s + ≤ 2 m − n + 1 , where s + denotes the sum of the squares of the positive eigenvalues. The conjecture is proved for various classes of graphs, including bipartite, regular, complete q -partite, hyper-energetic, and barbell graphs. Various searches have found no counter-examples. The paper concludes with a brief discussion of the apparent difficulties of proving the conjecture in general. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
41. Cospectral digraphs from locally line digraphs.
- Author
-
Dalfó, C. and Fiol, M.A.
- Subjects
- *
DIRECTED graphs , *GEOMETRIC vertices , *DE Bruijn graph , *DIAMETER , *SUBSET selection - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
42. Relation between signless Laplacian energy, energy of graph and its line graph.
- Author
-
Das, Kinkar Ch. and Mojallal, Seyed Ahmad
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *ABSOLUTE value , *MATHEMATICAL bounds , *MATHEMATICAL analysis , *NUMERICAL analysis - Abstract
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 ( L G ) ( L G is the line graph of G ) and LE + ( G ) , respectively. In this paper we obtain a relation between E ( L G ) and LE + ( G ) of graph G . From this relation we characterize all the graphs satisfying E ( L G ) = LE + ( G ) + 4 m n − 4 . We also present a relation between E ( G ) and E ( L G ) . Moreover, we give an upper bound on E ( L G ) of graph G and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
43. Extremal graphs with bounded vertex bipartiteness number.
- Author
-
Robbiano, María, Tapia Morales, Katherine, and San Martín, Bernardo
- Subjects
- *
GRAPH theory , *MATHEMATICAL bounds , *GEOMETRIC vertices , *BIPARTITE graphs , *NUMBER theory , *SET theory - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
44. Successful pressing sequences for a bicolored graph and binary matrices.
- Author
-
Cooper, Joshua and Davis, Jeffrey
- Subjects
- *
GRAPH theory , *BINARY codes , *MATRICES (Mathematics) , *LINEAR algebra , *GROUP theory - Abstract
We apply matrix theory over F 2 to understand the nature of so-called “successful pressing sequences” of black-and-white vertex-colored graphs. These sequences arise in computational phylogenetics, where, by a celebrated result of Hannenhalli and Pevzner, the space of sortings-by-reversal of a signed permutation can be described by pressing sequences. In particular, we offer several alternative linear-algebraic and graph-theoretic characterizations of successful pressing sequences, describe the relation between such sequences, and provide bounds on the number of them. We also offer several open problems that arose as a result of the present work. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
45. Maximizing the spectral radius of k-connected graphs with given diameter.
- Author
-
Huang, Peng, Shiu, Wai Chee, and Sun, Pak Kiu
- Subjects
- *
SPECTRAL theory , *RADIUS (Geometry) , *GRAPH connectivity , *DIAMETER , *EIGENVALUES , *MATRICES (Mathematics) - Abstract
The spectral radius of a graph is the largest eigenvalue of its adjacency matrix. P. Hansen and D. Stevanović (2008) [9] determined the graphs with maximum spectral radius among all connected graphs of order n with diameter D . In this paper, we generalize this result to k -connected graphs of order n with diameter D . [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
46. A note on connected bipartite graphs of fixed order and size with maximal index.
- Author
-
Petrović, Miroslav and Simić, Slobodan K.
- Subjects
- *
BIPARTITE graphs , *MAXIMAL subgroups , *EIGENVALUES , *MATRICES (Mathematics) , *GRAPH theory , *MATHEMATICAL analysis - Abstract
In this paper the unique graph with maximal index (i.e. the largest eigenvalue of the adjacency matrix) is identified among all connected bipartite graphs of order n and size n + k , under the assumption that k ≥ 0 and n ≥ k + 5 . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
47. Spectral characterizations of signed lollipop graphs.
- Author
-
Belardo, Francesco and Petecki, Paweł
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *MATHEMATICAL analysis , *BOUNDARY value problems , *NUMERICAL analysis - Abstract
Let Γ = ( G , σ ) be a signed graph, where G is the underlying simple graph and σ : E ( G ) → { + , − } is the sign function on the edges of G . In this paper we consider the spectral characterization problem extended to the adjacency matrix and Laplacian matrix of signed graphs. After giving some basic results, we study the spectral determination of signed lollipop graphs, and we show that any signed lollipop graph is determined by the spectrum of its Laplacian matrix. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
48. A formula for all minors of the adjacency matrix and an application
- Author
-
Bapat R. B., Lal A. K., and Pati S.
- Subjects
adjacency matrix ,linear subgraphs ,minors ,path bundle ,05c50 ,05c05 ,15a18 ,Mathematics ,QA1-939 - Abstract
We supply a combinatorial description of any minor of the adjacency matrix of a graph. This descriptionis then used to give a formula for the determinant and inverse of the adjacency matrix, A(G), of agraph G, whenever A(G) is invertible, where G is formed by replacing the edges of a tree by path bundles.
- Published
- 2014
- Full Text
- View/download PDF
49. Energy of inverse graphs of dihedral and symmetric groups
- Author
-
Ejima, O., AREMU, K. O., and Audu, A.
- Published
- 2020
- Full Text
- View/download PDF
50. Non-bipartite graphs of fixed order and size that minimize the least eigenvalue.
- Author
-
Jovović, Ivana, Koledin, Tamara, and Stanić, Zoran
- Subjects
- *
BIPARTITE graphs , *EIGENVALUES , *SET theory , *MATHEMATICAL constants , *MATHEMATICAL analysis - Abstract
In this paper we determine the unique graph with minimal least eigenvalue (of the adjacency matrix) within the set of connected graphs of fixed order n and size m , whenever m = ⌈ n 2 ⌉ ⌊ n 2 ⌋ + a , where a is a fixed integral constant in [ 1 , ⌈ n 2 ⌉ − 1 ] . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.