135 results on '"Adjacency matrix"'
Search Results
2. Some Properties of Double Domination in Vague Graphs with an Application.
- Author
-
Rao, Yongsheng, Cai, Ruiqi, Talebi, Ali Asghar, and Mojahedfar, Masomeh
- Subjects
- *
GRAPH theory , *DOMINATING set , *FUZZY graphs , *ENERGY consumption , *SYMMETRY - Abstract
This paper is devoted to the study of the double domination in vague graphs, and it is a contribution to the Special Issue "Advances in graph theory and Symmetry/Asymmetry" of Symmetry. Symmetry is one of the most important criteria that illustrate the structure and properties of fuzzy graphs. It has many applications in dominating sets and helps find a suitable place for construction. Vague graphs (VGs), which are a family of fuzzy graphs (FGs), are a well-organized and useful tool for capturing and resolving a range of real-world scenarios involving ambiguous data. In the graph theory, a dominating set (DS) for a graph G * = (X , E) is a subset D of the vertices X so that every vertex which is not in D is adjacent to at least one member of D. The subject of energy in graph theory is one of the most attractive topics serving a very important role in biological and chemical sciences. Hence, in this work, we express the notion of energy on a dominating vague graph (DVG) and also use the concept of energy in modeling problems related to DVGs. Moreover, we introduce a new notion of a double dominating vague graph (DDVG) and provide some examples to explain various concepts introduced. Finally, we present an application of energy on DVGs. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
3. Some New Bounds for α -Adjacency Energy of Graphs.
- Author
-
Zhang, Haixia and Zhang, Zhuolin
- Subjects
- *
GRAPH theory , *EIGENVALUES , *STRUCTURAL analysis (Engineering) , *ENERGY consumption - Abstract
Let G be a graph with the adjacency matrix A (G) , and let D (G) be the diagonal matrix of the degrees of G. Nikiforov first defined the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , 0 ≤ α ≤ 1 , which shed new light on A (G) and Q (G) = D (G) + A (G) , and yielded some surprises. The α − adjacency energy E A α (G) of G is a new invariant that is calculated from the eigenvalues of A α (G) . In this work, by combining matrix theory and the graph structure properties, we provide some upper and lower bounds for E A α (G) in terms of graph parameters (the order n, the edge size m, etc.) and characterize the corresponding extremal graphs. In addition, we obtain some relations between E A α (G) and other energies such as the energy E (G) . Some results can be applied to appropriately estimate the α -adjacency energy using some given graph parameters rather than by performing some tedious calculations. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. Graph Theory: A Lost Component for Development in Nigeria.
- Author
-
Babarinsa, Olayiwola
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *MATHEMATICS , *RESEARCH - Abstract
Graph theory is one of the neglected branches of mathematics in Nigeria but with the most applications in other fields of research. This article shows the paucity, importance, and necessity of graph theory in the development of Nigeria. The adjacency matrix and dual graph of the Nigeria map were presented. The graph spectrum and energies (graph energy and Laplacian energy) of the dual graph were computed. Then the chromatic number, maximum degree, minimum spanning tree, graph radius, and diameter, the Eulerian circuit and Hamiltonian paths from the dual graph were obtained and discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
5. Two upper bounds on the Aα-spectral radius of a connected graph.
- Author
-
Pirzada, Shariefuddin
- Subjects
- *
GRAPH theory , *GEOMETRIC vertices , *EIGENVALUES , *SUBGRAPHS , *GENERALIZATION - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
6. Change of nullity of a graph under two operations.
- Author
-
Mohiaddin, Gohdar H. and Sharaf, Khidir R.
- Subjects
- *
INDEPENDENT variables , *GRAPH theory , *EIGENVALUES , *MULTIPLICITY (Mathematics) - Abstract
The nullity of a graph G is the multiplicity of zero as an eigenvalue of its adjacency matrix. An assignment of weights to the vertices of a graph, that satisfies a zero sum condition over the neighbors of each vertex, and uses maximum number of independent variables is denoted by a high zero sum weighting of the graph. This applicable tool is used to determine the nullity of the graph. Two types of graphs are defined, and the change of their nullities is studied, namely, the graph G+ab constructed from G by adding a new vertex ab which is joint to all neighbors of both vertices a and b of G, and G•ab which is obtained from G+ab by removing both vertices a and b. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
7. A spherical evolution algorithm with two-stage search for global optimization and real-world problems.
- Author
-
Wang, Yirui, Cai, Zonghui, Guo, Lijun, Li, Guoqing, Yu, Yang, and Gao, Shangce
- Subjects
- *
GLOBAL optimization , *SEARCH algorithms , *TIME complexity , *GRAPH theory , *COMPUTATIONAL complexity - Abstract
This paper proposes a spherical evolution algorithm with two-stage search. Spherical search and hypercube search are combined to achieve individuals' evolution. A self-adaptive Gaussian scale factor and a variable scale factor are designed to adaptively control individuals' spherical and hypercube search area according to their search situations. Two search stages frequently switch with four search cases to enhance the balance between exploration and exploitation processes. A directed adjacency matrix is devised to analyze the relationship among individuals from the perspective of graph theory. Experiments compare the proposed algorithm with five algorithms with distinctive search patterns on twenty nine CEC2017 benchmark functions. The diversity analysis and graph theory analysis show the good population diversity and effective information spreading of the proposed algorithm. Twenty two real-world problems evaluate the practicality and optimization ability of the proposed algorithm. Finally, the computational time complexity demonstrates that the proposed algorithm is more efficient than the original spherical evolution algorithm. • A spherical evolution algorithm with two-stage search is proposed. • Spherical search and hypercube search are combined to adaptively guide individuals' evolution. • A directed adjacency matrix is firstly introduced to analyze the relationship among individuals. • Functions and real-world problems verify the superior search performance of the proposed algorithm. • The computational efficiency of the proposed algorithm is enhanced. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
8. The magnetic discrete Laplacian inferred from the Gauß–Bonnet operator and application.
- Author
-
Athmouni, Nassim, Baloudi, Hatem, Damak, Mondher, and Ennaceur, Marwa
- Subjects
- *
WEIGHTED graphs , *GRAPH theory , *SPECTRAL theory - Abstract
We consider the notion of χ -completeness of a locally finite graph and we extend this notion to the weighted magnetic graph. Moreover, we establish a link between the magnetic adjacency matrix on line graph and the magnetic discrete Laplacian on 1-forms. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
9. A Poisson multi-Bernoulli mixture filter for tracking multiple resolvable group targets.
- Author
-
Zhou, Yusong, Zhao, Jin, Wu, Sunyong, and Liu, Chang
- Subjects
- *
FILTERS & filtration , *GRAPH theory , *MIXTURES , *FUNCTIONALS , *DYNAMIC models - Abstract
This paper presents a novel Poisson multi-Bernoulli mixture (PMBM) filter for tracking multiple resolvable group targets (MRGT) based on graph theory. Firstly, the number of groups and the relationships between members within the group are modelled by the adjacency matrix. Then, considering that a single dynamic evolution model is insufficient to guarantee stable tracking performance for group targets, the virtual leader-follower model (VLFM) is introduced to predict the evolution trend of unknown and potentially detected targets, respectively. Furthermore, we prove the conjugation of the proposed algorithm with the probability generating functionals (PGF) and give a detailed implementation of the Gaussian mixture (GM). Based on the coexistence scenario of splitting, merging and non-linear motion of the group targets, the simulation results show the effectiveness of the proposed algorithm in comparison with the existing methods. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
10. A Unified Framework for Structured Graph Learning via Spectral Constraints.
- Author
-
Kumar, Sandeep, Jiaxi Ying, de M. Cardoso, Jose Vinícius, and Palomar, Daniel P.
- Subjects
- *
COMBINATORIAL optimization , *GRAPH theory , *REGULAR graphs , *SPECTRAL theory , *LAPLACIAN matrices , *NP-hard problems , *CONSTRAINT programming - Abstract
Graph learning from data is a canonical problem that has received substantial attention in the literature. Learning a structured graph is essential for interpretability and identification of the relationships among data. In general, learning a graph with a specific structure is an NP-hard combinatorial problem and thus designing a general tractable algorithm is challenging. Some useful structured graphs include connected, sparse, multi-component, bipartite, and regular graphs. In this paper, we introduce a unified framework for structured graph learning that combines Gaussian graphical model and spectral graph theory. We propose to convert combinatorial structural constraints into spectral constraints on graph matrices and develop an optimization framework based on block majorization-minimization to solve structured graph learning problem. The proposed algorithms are provably convergent and practically amenable for a number of graph based applications such as data clustering. Extensive numerical experiments with both synthetic and real data sets illustrate the effectiveness of the proposed algorithms. An open source R package containing the code for all the experiments is available at https://CRAN.R-project.org/package=spectralGraphTopology. [ABSTRACT FROM AUTHOR]
- Published
- 2020
11. Uniquely pressable graphs: Characterization, enumeration, and recognition.
- Author
-
Cooper, Joshua and Whitlatch, Hays
- Subjects
- *
GRAPHIC methods , *GRAPH theory , *ALGORITHMS , *MATHEMATICAL models , *NUMERICAL analysis - Abstract
Abstract Motivated by the study of genomes evolving by reversals, we consider pseudograph transformations known as "pressing sequences". In particular, we address the question of when a graph has precisely one pressing sequence resulting in the empty graph, thus answering an question from Cooper and Davis (2015) [13]. We characterize such "uniquely pressable" graphs, count the number of them on a given number of vertices, and provide a polynomial-time recognition algorithm. We conclude with several open questions. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
12. On graphs with prescribed star complements.
- Author
-
Yuan, Xiying, Zhao, Qingqing, Liu, Lele, and Chen, Hongyan
- Subjects
- *
GRAPH theory , *MULTIPLICITY (Mathematics) , *LOCALIZATION (Mathematics) , *FRACTIONAL calculus , *TREE graphs - Abstract
Abstract Let μ be an eigenvalue of a simple graph G with multiplicity k ≥ 1. A star complement for μ in G is an induced subgraph of G of order n − k with no eigenvalue μ. In this paper, we study the maximal graphs with the star S m as a star complement for −2. The maximal graphs with S 3 , S 4 , S 13 and S 21 as a star complement for −2 are described. We also describe the regular graphs with K 2 , s (s ≥ 2) as a star complement for an eigenvalue μ. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
13. 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
14. 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
15. Numerical Range of Simple Graphs and Some Bounds for their Eigenvalues.
- Author
-
Tajarrod, M. and Sistani, T.
- Subjects
- *
CHARTS, diagrams, etc. , *MATRICES (Mathematics) , *APPROXIMATION algorithms , *EIGENVALUE equations , *SUBGRAPHS - Abstract
The numerical range of a simple graph G, named F(G), is the numerical range of its adjacency matrix A(G). The main purpose of this paper is to approximate F(G). Then, using this approximation, bounds for the largest and the smallest eigenvalues of G are proposed. In fact, lower bounds for the largest eigenvalues of G are presented in terms of disjoint induced subgraphs of G and the numerical range of the square of A(G). [ABSTRACT FROM AUTHOR]
- Published
- 2018
16. 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
17. 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
18. 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
19. 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
20. On the determinant of the Laplacian matrix of a complex unit gain graph.
- Author
-
Wang, Yi, Gong, Shi-Cai, and Fan, Yi-Zheng
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *MATHEMATICAL complexes , *UNDIRECTED graphs , *PATHS & cycles in graph theory - Abstract
Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
21. Improved McClelland and Koolen-Moulton bounds for the energy of graphs.
- Author
-
Sridhara, G., Kanna, M. R. Rajesh, Jagadeesh, R., and Cangul, I. N.
- Subjects
- *
GRAPH theory , *CARBON compounds , *GRAPHIC methods , *ELECTRONS , *CHEMISTRY - Abstract
Given a graph G with n vertices and m edges, the term energy of graph E(G) was introduced by Gutman in chemistry, due to its relevance to the total π ― electron energy of carbon compounds. In 1971 McClelland obtained both lower and upper bounds for π 8213; electron energy. An improved upper bound was obtained by Koolen-Moulton in 2001. The lower and upper bounds for E(G) obtained in this paper are better than McClelland and Koolen-Moulton bounds. Also we obtained an upper bound for graph energy in terms of n as E(G) ≤ n/2[ 1 + √ n-2/2]. [ABSTRACT FROM AUTHOR]
- Published
- 2018
22. Minimizing graph of the connected graphs whose complements are bicyclic with two cycles.
- Author
-
JAVAID, Muhammad
- Subjects
- *
BICYCLIC compounds , *GRAPH connectivity , *GRAPHIC methods , *GRAPH theory , *GEOMETRIC vertices , *EIGENVALUES - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
23. 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
24. 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
25. 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
26. 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
27. MERGING THE A- AND Q-SPECTRAL THEORIES.
- Author
-
Nikiforov, V.
- Subjects
- *
MATRICES (Mathematics) , *LAPLACIAN operator , *GRAPH theory , *CONVEX functions , *MATHEMATICAL models - Abstract
Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G: The signless Laplacian Q(G) of G is defined as Q(G) := A(G) +D(G). Cvetković called the study of the adjacency matrix the A-spectral theory, and the study of the signless Laplacian-the Q-spectral theory. To track the gradual change of A(G) into Q(G), in this paper it is suggested to study the convex linear combinations Aα(G) of A(G) and D(G) defined byAα (G) := αD(G) + (1 - α )A(G) , 0 ≤ α ≤ 1. This study sheds new light on A(G) and Q(G), and yields, in particular, a novel spectral Turán theorem. A number of open problems are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
28. A NOTE ON THE NORDHAUS-GADDUM TYPE INEQUALITY TO THE SECOND LARGEST EIGENVALUE OF A GRAPH.
- Author
-
Abreu, Nair, Brondani, André E., de Lima, Leonardo, and Oliveira, Carla
- Subjects
- *
EIGENVALUES , *GRAPH theory , *GEOMETRIC vertices , *POLYNOMIALS , *MATHEMATICAL models - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
29. Hamming index of some thorn graphs with respect to adjacency matrix.
- Author
-
Ramane, Harishchandra S., Gudodagi, Gouramma A., and Yalnaik, Ashwini S.
- Subjects
- *
GRAPH theory , *HAMMING distance , *GEOMETRIC vertices , *MATRICES (Mathematics) , *SET theory - Abstract
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]
- Published
- 2016
30. Non-Singular graphs with a Singular Deck.
- Author
-
Farrugia, Alexander, Gauci, John Baptist, and Sciriha, Irene
- Subjects
- *
GRAPH theory , *MATHEMATICAL symmetry , *MATRICES (Mathematics) , *MOLECULAR graphs , *ELECTRICAL conductors , *SUBGRAPHS - Abstract
The n -vertex graph G ( = Γ ( G ) ) with a non-singular real symmetric adjacency matrix G , having a zero diagonal and singular ( n − 1 ) × ( n − 1 ) principal submatrices is termed a NSSD, a Non-Singular graph with a Singular Deck. NSSDs arose in the study of the polynomial reconstruction problem and were later found to characterise non-singular molecular graphs that are distinct omni-conductors and ipso omni-insulators. Since both matrices G and G − 1 represent NSSDs Γ ( G ) and Γ ( G − 1 ) , the value of the nullity of a one-, two- and three-vertex deleted subgraph of G is shown to be determined by the corresponding subgraph in Γ ( G − 1 ) . Constructions of infinite subfamilies of non-NSSDs are presented. NSSDs with all two-vertex deleted subgraphs having a common value of the nullity are referred to as G -nutful graphs. We show that their minimum vertex degree is at least 4. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
31. 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
32. 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
33. 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
34. Quantum Probability Aspects to Lexicographic and Strong Products of Graphs.
- Author
-
Nobuaki OBATA
- Subjects
- *
QUANTUM information theory , *PROBABILITY theory , *GRAPH theory , *MATHEMATICAL decomposition , *RANDOM variables , *DISTRIBUTION (Probability theory) - Abstract
The adjacency matrix of the lexicographic product of graphs is decomposed into a sum of monotone independent random variables in a certain product state. The adjacency matrix of the strong product of graphs admits an expression in terms of commutative independent random variables in a product state. Their spectral distributions are obtained by using the monotone, classical and Mellin convolutions of probability distributions. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
35. On The Eigenvalue Distribution Of Adjacency Matrices For Connected Planar Graphs.
- Author
-
Griffith, Daniel A.
- Subjects
- *
EIGENVALUES , *GRAPH theory , *PLANAR graphs , *LEAST squares , *PARAMETER estimation , *DISTRIBUTION (Probability theory) - Abstract
This paper describes the previously unknown statistical distribution of adjacency matrix spectra for planar graphs, also known as spatial weights matrices, in terms of the following three readily available eigenvalue properties: extremes, rank orderings, and sums of powers. This distribution is governed by at most six parameters that, once known, allow accurate approximations of eigenvalues to be computed without resorting to numerical matrix methods applied on a case-by-case basis. Parameter estimates for illustrative real-world examples are obtained using nonlinear least squares regression techniques. Three conjectures are proposed, and graphical and trend results are reported for a diverse set of planar graph-based matrices. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
36. 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
37. 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
38. On the multiplicity of the adjacency eigenvalues of graphs.
- Author
-
Bahmani, Asghar and Kiani, Dariush
- Subjects
- *
MULTIPLICITY (Mathematics) , *GRAPH theory , *EIGENVALUES , *MATRICES (Mathematics) , *MATHEMATICAL analysis - Abstract
Let G be a simple graph with the adjacency matrix A ( G ) . A well-known result of Cvetković and Gutman states that removing a pendant vertex and its neighbour, does not change the nullity of the graph. We generalize this theorem and some other theorems similar to it for an arbitrary eigenvalue of a graph. Also, for an arbitrary eigenvalue λ , we use a corresponding star set to delete some subgraphs and to determine the multiplicity of λ . We use star sets to find some Parter–Wiener vertices, in trees. We state our results for real symmetric matrices (and so for weighted graphs) and as a corollary we use them for simple graphs. Furthermore, we use these methods to obtain some results for λ = 0 , ± 1 . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
39. The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic.
- Author
-
Wang, Yi, Fan, Yi-Zheng, Li, Xiao-Xin, and Zhang, Fei-Fei
- Subjects
- *
EIGENVALUES , *GRAPH theory , *SET theory , *GRAPH connectivity , *MATHEMATICAL analysis - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
40. Every totally real algebraic integer is a tree eigenvalue.
- Author
-
Salez, Justin
- Subjects
- *
ALGEBRA , *INTEGERS , *TREE graphs , *EIGENVALUES , *GRAPH theory - Abstract
Graph eigenvalues are examples of totally real algebraic integers, i.e. roots of real-rooted monic polynomials with integer coefficients. Conversely, the fact that every totally real algebraic integer occurs as an eigenvalue of some finite graph is a deep and remarkable result, conjectured forty years ago by Hoffman, and proved seventeen years later by Estes. This short paper provides an independent and elementary proof of a stronger statement, namely that the graph may actually be chosen to be a tree. As a by-product, our result implies that the atoms of the limiting spectrum of n × n symmetric matrices with independent Bernoulli ( c n ) entries are exactly the totally real algebraic integers. This settles an open problem raised by Ben Arous (2010). [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
41. Notes on the second largest eigenvalue of a graph.
- Author
-
Simić, Slobodan K., Anđelić, Milica, da Fonseca, Carlos M., and Živković, Dejan
- Subjects
- *
EIGENVALUES , *GRAPH theory , *LAPLACIAN matrices , *VERTEX operator algebras , *POLYNOMIALS - Abstract
For a fixed real number r we give several necessary and/or sufficient conditions for a graph to have the second largest eigenvalue of the adjacency matrix, or signless Laplacian matrix, less then or equal to r . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
42. Eigenvalues and energy in threshold graphs.
- Author
-
Jacobs, David P., Trevisan, Vilmar, and Tura, Fernando
- Subjects
- *
EIGENVALUES , *MATHEMATICAL sequences , *THRESHOLDING algorithms , *GRAPH theory , *MATRICES (Mathematics) - Abstract
Assuming a uniform random model of selecting creation sequences, we show that almost every connected threshold graph has more negative than positive eigenvalues. We show that no threshold graphs have eigenvalues in ( − 1 , 0 ) . Sequences of equienergetic graphs are given including the striking result that for all n ≥ 3 , there exist n − 1 threshold graphs of order n 2 , pairwise noncospectral, each equienergetic to K n 2 . For all n > 8 , we find an n -vertex hyperenergetic threshold graph. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
43. State transfer and star complements in graphs.
- Author
-
Jiang Zhou and Changjiang Bu
- Subjects
- *
GRAPH theory , *EIGENVALUES , *MULTIPLICITY (Mathematics) , *OPERATOR theory , *MATRIX groups , *MATHEMATICAL analysis - Abstract
Let G be a graph with adjacency matrix A, and let H(t)=exp(itA). For an eigenvalue μ of A with multiplicity k, a star set for μ in G is a vertex set X of G such that |X|=k and the induced subgraph G-X does not have μ as an eigenvalue. G is said to have perfect state transfer from the vertex u to the vertex v if there is a time τ such that |H(τ)u,v|=1. The unitary operator H(t) has important applications in the transfer of quantum information. In this paper, we give an expression of H(t). For a star set X of graph G, perfect state transfer does not occur between any two vertices in X. We also give some results for the existence of perfect state transfer in a graph. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
44. Matrix power inequalities and the number of walks in graphs.
- Author
-
Täubig, Hanjo and Weihmann, Jeremias
- Subjects
- *
MATRIX inequalities , *GRAPH theory , *NUMBER theory , *MATHEMATICS theorems , *SET theory , *MATHEMATICAL bounds - Abstract
We unify and generalize several inequalities for the number wk of walks of length k in graphs, and for the entry sum of matrix powers. First, we present a weighted sandwich theorem for Hermitian matrices which generalizes a matrix theorem by Marcus and Newman and which further generalizes our former unification of inequalities for the number of walks in undirected graphs by Lagarias et al. and by Dress and Gutman. The new inequality uses an arbitrary nonnegative weighting of the indices (vertices) which allows to apply the theorem to index (vertex) subsets (i.e., inequalities considering the number wk(S,S) of walks of length k that start at a vertex of a given vertex subset S and that end within the same subset). We also deduce a stronger variation of the sandwich theorem for the case of positive-semidefinite Hermitian matrices which generalizes another inequality of Marcus and Newman. Further, we show a similar theorem for nonnegative symmetric matrices which is another unification and generalization of inequalities for walk numbers by Erdős and Simonovits, by Dress and Gutman, and by Ilić and Stevanović. In the last part, we generalize lower bounds for the spectral radius of adjacency matrices and upper bounds for the energy of graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
45. TWO GRAPHS WITH A COMMON EDGE.
- Author
-
BADURA, LIDIA
- Subjects
- *
GRAPH theory , *PATHS & cycles in graph theory , *DETERMINANTS (Mathematics) , *SUBGRAPHS , *MATRICES (Mathematics) , *MATHEMATICAL analysis - 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 detA(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 [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
46. The inertia of weighted unicyclic graphs.
- Author
-
Yu, Guihai, Zhang, Xiao-Dong, and Feng, Lihua
- Subjects
- *
WEIGHTED graphs , *GRAPH theory , *NUMBER theory , *EIGENVALUES , *MATRICES (Mathematics) , *MULTIPLICITY (Mathematics) - Abstract
Abstract: Let be a weighted graph. The inertia of is the triple , where , , are the numbers of the positive, negative and zero eigenvalues of the adjacency matrix of including their multiplicities, respectively. , are called the positive, negative indices of inertia of , respectively. In this paper we present a lower bound for the positive, negative indices of weighted unicyclic graphs of order n with fixed girth and characterize all weighted unicyclic graphs attaining this lower bound. Moreover, we characterize the weighted unicyclic graphs of order n with two positive, two negative and at least zero eigenvalues, respectively. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
47. On two conjectures of Randić index and the largest signless Laplacian eigenvalue of graphs.
- Author
-
Deng, Hanyuan, Balachandran, S., and Ayyaswamy, S.K.
- Subjects
- *
EIGENVALUES , *GRAPH theory , *LAPLACIAN matrices , *HARMONIC analysis (Mathematics) , *MATHEMATICAL proofs , *MATHEMATICAL analysis - Abstract
Abstract: The Randić index R of a graph G is defined as the sum of over all edges of G, where denotes the degree of a vertex in G. is the largest eigenvalue of the signless Laplacian matrix of G, where D is the diagonal matrix with degrees of the vertices on the main diagonal and A is the adjacency matrix of G. Hansen and Lucas [18] conjectured (1) and equality holds for and (2) with equality if and only if for and for , respectively. In this paper, we prove the conjecture (1) and obtain a result very close to the conjecture (2). Moreover, we give some results relating harmonic index and the largest eigenvalue of the adjacency matrix. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
48. Smith forms for adjacency matrices of circulant graphs.
- Author
-
Williams, Gerald
- Subjects
- *
GRAPH theory , *PATHS & cycles in graph theory , *CIRCULANT matrices , *ABELIAN groups , *PROOF theory , *MATHEMATICAL analysis - Abstract
Abstract: We calculate the Smith normal form of the adjacency matrix of each of the following graphs or their complements (or both): complete graph, cycle graph, square of the cycle, power graph of the cycle, distance matrix graph of cycle, Andrásfai graph, Doob graph, cocktail party graph, crown graph, prism graph, Möbius ladder. The proofs operate by finding the abelianization of a cyclically presented group whose relation matrix is column equivalent to the required adjacency matrix. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
49. A note on the multiplicities of graph eigenvalues.
- Author
-
Bu, Changjiang, Zhang, Xu, and Zhou, Jiang
- Subjects
- *
MULTIPLICITY (Mathematics) , *GRAPH theory , *EIGENVALUES , *SET theory , *PATHS & cycles in graph theory , *SYMMETRIC matrices , *TREE graphs - Abstract
Abstract: Let G be a graph with vertex set , and let H be the graph obtained by attaching one pendant path of length at vertex . For a real symmetric matrix A whose graph is H, let denote the multiplicity of an eigenvalue μ of A. From a result in da Fonseca (2005) [7], we know that . In this note, we characterize the case . We also give two upper bounds on eigenvalue multiplicity of trees and unicyclic graphs, which are generalizations of some results in Rowlinson (2010) [10]. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
50. Reflexive bipartite regular graphs.
- Author
-
Koledin, Tamara and Stanić, Zoran
- Subjects
- *
BIPARTITE graphs , *GRAPH theory , *REGULAR graphs , *EIGENVALUES , *MODULES (Algebra) - Abstract
Abstract: A graph is called reflexive if its second largest eigenvalue does not exceed 2. In this paper, we determine all reflexive bipartite regular graphs. Any bipartite regular graph of degree at most 2 is reflexive as well as its bipartite complement. Apart from them, there is a finite number of resulting graphs. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.