23 results on '"Adjacency matrix"'
Search Results
2. 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
3. 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
4. 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
5. The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic
- Author
-
Wang Yi, Fan Yi-Zheng, Li Xiao-Xin, and Zhang Fei-Fei
- Subjects
unicyclic graph ,complement ,adjacency matrix ,least eigen- value ,Mathematics ,QA1-939 - Abstract
A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and contains exactly one cycle (namely the class Ucn of graphs whose complements are unicyclic), and characterize the unique minimizing graph in Ucn when n ≥ 20.
- Published
- 2015
- Full Text
- View/download PDF
6. Two Graphs with a Common Edge
- Author
-
Badura Lidia
- Subjects
graph ,adjacency matrix ,determinant of graph ,path ,cycle ,Mathematics ,QA1-939 - Abstract
Let G = G1 ∪ G2 be the sum of two simple graphs G1,G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant det A(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples
- Published
- 2014
- Full Text
- View/download PDF
7. THE WALKS AND CDC OF GRAPHS WITH THE SAME MAIN EIGENSPACE.
- Author
-
SCIRIHA, IRENE and COLLINS, LUKE
- Subjects
- *
EIGENVECTORS , *EIGENVALUES , *ORTHOGRAPHIC projection - Abstract
The main eigenvalues of a graph G are those eigenvalues of the (0; 1)- adjacency matrix A with a corresponding eigenspace not orthogonal to j = (1 /1/ ... j 1)T. The principal main eigenvector associated with a main eigenvalue is the orthogonal projection of the corresponding eigenspace onto j. The main eigenspace of a graph is generated by all the principal main eigenvectors and is the same as the image of the walk matrix. We explore a new concept to see to what extent the main eigenspace determines the entries of the walk matrix of a graph. The CDC of a graph G is the direct product G x K2. We establish a hierarchy of inclusions connecting classes of graphs in view of their CDC, walk matrix, main eigenvalues and main eigenspaces. We provide a new proof that graphs with the same CDC are characterized as TF-isomorphic graphs. A complete list of TF-isomorphic graphs on at most 8 vertices and their common CDC is also given. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
8. ON THE DISPLACEMENT OF EIGENVALUES WHEN REMOVING A TWIN VERTEX.
- Author
-
BRIFFA, JOHANN A. and SCIRIHA, IRENE
- Subjects
- *
POLYNOMIALS , *NEIGHBORHOODS , *MATRICES (Mathematics) - Abstract
Twin vertices of a graph have the same open neighbourhood. If they are not adjacent, then they are called duplicates and contribute the eigenvalue zero to the adjacency matrix. Otherwise they are termed co-duplicates, when they contribute -1 as an eigenvalue of the adjacency matrix. On removing a twin vertex from a graph, the spectrum of the adjacency matrix does not only lose the eigenvalue 0 or -1. The perturbation sends a rippling effect to the spectrum. The simple eigenvalues are displaced. We obtain a closed formula for the characteristic polynomial of a graph with twin vertices in terms of two polynomials associated with the perturbed graph. These are used to obtain estimates of the displacements in the spectrum caused by the perturbation. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
9. ON SINGULAR SIGNED GRAPHS WITH NULLSPACE SPANNED BY A FULL VECTOR: SIGNED NUT GRAPHS.
- Author
-
BAŠIĆ, NINO, FOWLER, PATRICK W., PISANSKI, TOMAŽ, and SCIRIHA, IRENE
- Subjects
- *
INFINITE series (Mathematics) , *REGULAR graphs , *NUTS , *CHARTS, diagrams, etc. - Abstract
A signed graph has edge weights drawn from the set {+1, -1}, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which regular nut graphs with all edge weights +1 exist have been determined recently for the degrees up to 12. By extending the definition to signed graphs, we here find all pairs (ρ, n) for which a ρ-regular nut graph (sign-balanced or sign-unbalanced) of order n exists with ρ ≤ 11. We devise a construction for signed nut graphs based on a smaller 'seed' graph, giving infinite series of both sign-balanced and sign-unbalanced ρ-regular nut graphs. Orders for which a regular nut graph with ρ = n - 1 exists are characterised; they are sign-unbalanced with an underlying graph Kn for which n ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with ρ = n-2 exists are also characterised; they have an underlying cocktail-party graph CP(n) with even order n ≥ 8. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
10. SOME PROPERTIES OF THE EIGENVALUES OF THE NET LAPLACIAN MATRIX OF A SIGNED GRAPH.
- Author
-
STANIĆ, ZORAN
- Subjects
- *
EIGENVALUES , *LAPLACIAN matrices , *MATHEMATICAL bounds , *MATRICES (Mathematics) - Abstract
Given a signed graph Ġ, let A Ġ and D± Ġ denote its standard adjacency matrix and the diagonal matrix of vertex net-degrees, respectively. The net Laplacian matrix of Ġ is defined to be NĠ = D± Ġ -AĠ. In this study we give some properties of the eigenvalues of NĠ. In particular, we consider their behaviour under some edge perturbations, establish some relations between them and the eigenvalues of the standard Laplacian matrix and give some lower and upper bounds for the largest eigenvalue of NĠ. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
11. GRAPHS WITH ALL BUT TWO EIGENVALUES IN [-2, 0].
- Author
-
ABREU, NAIR, ALENCAR, JORGE, BRONDANI, ANDRÉ, DE LIMA, LEONARDO, and OLIVEIRA, CARLA
- Subjects
- *
EIGENVALUES , *COMPLETE graphs - Abstract
The eigenvalues of a graph are those of its adjacency matrix. Recently, Cioabă, Haemers and Vermette characterized all graphs with all but two eigenvalues equal to -2 and 0. In this article, we extend their result by characterizing explicitly all graphs with all but two eigenvalues in the interval [-2, 0]. Also, we determine among them those that are determined by their spectrum. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
12. SIGNED COMPLETE GRAPHS WITH MAXIMUM INDEX.
- Author
-
AKBARI, SAIEED, DALVANDI, SOUDABEH, HEYDARI, FARIDEH, and MAGHASEDI, MOHAMMAD
- Subjects
- *
COMPLETE graphs , *PATHS & cycles in graph theory , *EIGENVALUES , *GEOMETRIC vertices - 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. The adjacency matrix of a signed graph has -1 or +1 for adjacent vertices, depending on the sign of the edges. It was conjectured that if Γ is a signed complete graph of order n with k negative edges, k < n -- 1 and Γ has maximum index, then negative edges form K1,k. In this paper, we prove this conjecture if we confine ourselves to all signed complete graphs of order n whose negative edges form a tree of order k + 1. A [1, 2]-subgraph of G is a graph whose components are paths and cycles. Let Γ be a signed complete graph whose negative edges form a [1, 2]-subgraph. We show that the eigenvalues of Γ satisfy the following inequalities: --5 ≤ λn ≤ ... ≤ λ2 ≤ 3. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
13. GRAPHS WHOSE Aα-SPECTRAL RADIUS DOES NOT EXCEED 2.
- Author
-
JIAN FENG WANG, JING WANG, XIAOGANG LIU, and BELARDO, FRANCESCO
- Subjects
- *
RADIUS (Geometry) , *GRAPH connectivity - Abstract
Let A(G) and D(G) be the adjacency matrix and the degree matrix of a graph G, respectively. For any real α ∊ [0,1], we consider Aα(G) = αD(G) + (1 -- α)A(G) as a graph matrix, whose largest eigenvalue is called the Aα-spectral radius of G. We first show that the smallest limit point for the Aα-spectral radius of graphs is 2, and then we characterize the connected graphs whose Aα-spectral radius is at most 2. Finally, we show that all such graphs, with four exceptions, are determined by their Aα-spectra. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
14. DETERMINING GRAPHS BY THE COMPLEMENTARY SPECTRUM.
- Author
-
PINHEIRO, LUCÉIIA K., SOUZA, BRUNA S., and TREVISAN, VILMAR
- Subjects
- *
GRAPH connectivity , *SUBGRAPHS , *EIGENVALUES - Abstract
The complementary spectrum of a connected graph G is the set of the complementary eigenvalues of the adjacency matrix of G. In this note, we discuss the possibility of representing G using this spectrum. On one hand, we give evidence that this spectrum distinguishes more graphs than other standard graph spectra. On the other hand, we show that it is hard to compute the complementary spectrum. In particular, we see that computing the complementary spectrum is equivalent to finding all connected induced subgraphs. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
15. TURÁN'S THEOREM IMPLIES STANLEY'S BOUND.
- Author
-
NIKIFOROV, V.
- Subjects
- *
EDGES (Geometry) , *MATRICES (Mathematics) , *RADIUS (Geometry) - Abstract
Let G be a graph with m edges and let ρ be the largest eigenvalue of its adjacency matrix. It is shown that...improving the well-known bound of Stanley. Moreover, writing ω for the clique number of G and Wk for the number of its walks on k vertices, it is shown that the sequence...is nonincreasing and converges to ρ. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
16. GRAPHS WITH CLUSTERS PERTURBED BY REGULAR GRAPHS--Aα-SPECTRUM AND APPLICATIONS.
- Author
-
CARDOSO, DOMINGOS M., PASTÉN, GERMAIN, and ROJO, OSCAR
- Subjects
- *
REGULAR graphs , *GRAPH connectivity , *EIGENVALUES - Abstract
Given a graph G, its adjacency matrix A(G) and its diagonal matrix of vertex degrees D(G) consider the matrix Aα(G) = αD(G) + (1 -- α)A(G), where α ∊ [0,1). The Aα-spectrum of G is the multiset of eigenvalues of Aα(G) and these eigenvalues are the α-eigenvalues of G. A cluster in G is a pair of vertex subsets (C, S), where C is a set of cardinality |C| ≥ 2 of pairwise co-neighbor vertices sharing the same set S of |S| neighbors. Assuming that G is connected and it has a cluster (C, S), G(H) is obtained from G and an r-regular graph H of order |C| by identifying its vertices with the vertices in C, eigenvalues of Aα(G) and Aα(G(H)) are deduced and if Aα(H) is positive semidefinite, then the i-th eigenvalue of Aα(G(H)) is greater than or equal to i-th eigenvalue of Aα(G). These results are extended to graphs with several pairwise disjoint clusters (C1, S1), .. ., (Ck, Sk). As an application, the effect on the energy, α-Estrada index and α-index of a graph G with clusters when the edges of regular graphs are added to G are analyzed. Finally, the Aα-spectrum of the corona product G o H of a connected graph G and a regular graph H is determined. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
17. Unified Spectral Bounds on the Chromatic Number
- Author
-
Elphick Clive and Wocjan Pawel
- Subjects
chromatic number ,majorization ,Mathematics ,QA1-939 - Abstract
One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where μ1 and μn are respectively the maximum and minimum eigenvalues of the adjacency matrix: χ ≥ 1+μ1/−μn. We recently generalised this bound to include all eigenvalues of the adjacency matrix.
- Published
- 2015
- Full Text
- View/download PDF
18. CENTROSYMMETRIC GRAPHS AND A LOWER BOUND FOR GRAPH ENERGY OF FULLERENES.
- Author
-
KATONA, GYULA Y., FAGHANI, MORTEZA, and ASHRAFI, ALI REZA
- Subjects
- *
MATHEMATICAL symmetry , *GRAPH theory , *MATHEMATICAL bounds , *MOLECULAR graphs , *FULLERENES - Abstract
The energy of a molecular graph G is defined as the summation of the absolute values of the eigenvalues of adjacency matrix of a graph G. In this paper, an infinite class of fullerene graphs with 10n vertices, n ≥ 2, is considered. By proving centrosymmetricity of the adjacency matrix of these fullerene graphs, a lower bound for its energy is given. Our method is general and can be extended to other class of fullerene graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
19. ON THE NUMBER OF α-LABELED GRAPHS.
- Author
-
BARRIENTOS, CHRISTIAN and MINION, SARAH
- Subjects
- *
RANDOM graphs , *BOUNDARY value problems , *DIRECTED acyclic graphs , *BIPARTITE graphs , *REGULAR graphs - Abstract
When a graceful labeling of a bipartite graph places the smaller labels in one of the stable sets of the graph, it becomes an α-labeling. This is the most restrictive type of difference-vertex labeling and it is located at the very core of this research area. Here we use an extension of the adjacency matrix to count and classify α-labeled graphs according to their size, order, and boundary value. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
20. ON THE SPECTRAL CHARACTERIZATIONS OF GRAPHS.
- Author
-
JING HUANG and SHUCHAO LI
- Subjects
- *
LAPLACIAN matrices , *REGULAR graphs , *GEOMETRIC vertices , *EIGENVALUES , *MATHEMATICS theorems - Abstract
Several matrices can be associated to a graph, such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question "Which graphs are determined by their spectrum?" is still a difficult problem in spectral graph theory. Let U2qp be the set of graphs obtained from Cp by attaching two pendant edges to each of q (q ≤ p) vertices on Cp, whereas V2qp the subset of U2qp with odd p and its q vertices of degree 4 being nonadjacent to each other. In this paper, we show that each graph in U 2q p , p even and its q vertices of degree 4 being consecutive, is determined by its Laplacian spectrum. As well we show that if G is a graph without isolated vertices and adjacency cospectral with the graph in Vp-1p = {H}, then G ≃= H. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
21. Graphs with Clusters Perturbed by Regular Graphs—Aα-Spectrum and Applications
- Author
-
Cardoso Domingos M., Pastén Germain, and Rojo Oscar
- Subjects
cluster ,convex combination of matrices ,aα-spectrum ,corona product of graphs ,05e30 ,15a18 ,05c50 ,Mathematics ,QA1-939 - Abstract
Given a graph G, its adjacency matrix A(G) and its diagonal matrix of vertex degrees D(G), consider the matrix Aα (G) = αD(G) + (1 − α)A(G), where α ∈ [0, 1). The Aα -spectrum of G is the multiset of eigenvalues of Aα (G) and these eigenvalues are the α-eigenvalues of G. A cluster in G is a pair of vertex subsets (C, S), where C is a set of cardinality |C| ≥ 2 of pairwise co-neighbor vertices sharing the same set S of |S| neighbors. Assuming that G is connected and it has a cluster (C, S), G(H) is obtained from G and an r-regular graph H of order |C| by identifying its vertices with the vertices in C, eigenvalues of Aα (G) and Aα (G(H)) are deduced and if Aα (H) is positive semidefinite, then the i-th eigenvalue of Aα (G(H)) is greater than or equal to i-th eigenvalue of Aα (G). These results are extended to graphs with several pairwise disjoint clusters (C1, S1), . . . , (Ck, Sk). As an application, the effect on the energy, α-Estrada index and α-index of a graph G with clusters when the edges of regular graphs are added to G are analyzed. Finally, the Aα-spectrum of the corona product G ◦ H of a connected graph G and a regular graph H is determined.
- Published
- 2020
- Full Text
- View/download PDF
22. Graphs Whose Aα -Spectral Radius Does Not Exceed 2
- Author
-
Wang Jian Feng, Wang Jing, Liu Xiaogang, and Belardo Francesco
- Subjects
aα -matrix ,smith graphs ,limit point ,spectral radius ,index ,05c50 ,Mathematics ,QA1-939 - Abstract
Let A(G) and D(G) be the adjacency matrix and the degree matrix of a graph G, respectively. For any real α ∈ [0, 1], we consider Aα (G) = αD(G) + (1 − α)A(G) as a graph matrix, whose largest eigenvalue is called the Aα -spectral radius of G. We first show that the smallest limit point for the Aα -spectral radius of graphs is 2, and then we characterize the connected graphs whose Aα -spectral radius is at most 2. Finally, we show that all such graphs, with four exceptions, are determined by their Aα -spectra.
- Published
- 2020
- Full Text
- View/download PDF
23. On the Spectral Characterizations of Graphs
- Author
-
Huang Jing and Li Shuchao
- Subjects
laplacian spectrum ,adjacency spectrum ,cospectral graphs ,spectral characterization ,05c50 ,15a18 ,Mathematics ,QA1-939 - Abstract
Several matrices can be associated to a graph, such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question “Which graphs are determined by their spectrum?” is still a difficult problem in spectral graph theory. Let 𝒰p2q${\cal U}_p^{2q}$ be the set of graphs obtained from Cp by attaching two pendant edges to each of q (q ⩽ p) vertices on Cp, whereas 𝒱p2q${\cal V}_p^{2q}$ the subset of 𝒰p2q${\cal U}_p^{2q}$ with odd p and its q vertices of degree 4 being nonadjacent to each other. In this paper, we show that each graph in 𝒰p2q${\cal U}_p^{2q}$ , p even and its q vertices of degree 4 being consecutive, is determined by its Laplacian spectrum. As well we show that if G is a graph without isolated vertices and adjacency cospectral with the graph in 𝒱pp−1={H}${\cal V}_p^{p - 1} = \{ H\}$ , then G ≅ H.
- Published
- 2017
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.